위상 정렬(topological sort)에 대한 설명으로 옳은 것은? | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
위상 정렬(topological sort)에 대한 설명으로 옳은 것은?
1
깊이 우선 탐색 방식을 이용해서는 구현할 수 없다.
2
하나의 그래프에 한 개의 위상 정렬만 존재한다.
3
사이클이 없는 모든 종류의 그래프에 적용할 수 있다.
4
간선 <i, j>를 가질 때 정점 i는 정점 j를 선행한다.
해설
옳은 설명은 간선 <i, j>가 있으면 정점 i가 정점 j를 선행한다는 것이다.
위상 정렬은 방향 비순환 그래프(DAG)의 정점을 모든 간선 i→j에 대해 i가 j보다 앞에 오도록 나열하는 것이다.
- DFS의 종료 순서를 역순으로 나열하는 방식으로 위상 정렬을 구현할 수 있다.
- 선후 관계가 없는 정점들의 순서는 바꿀 수 있으므로 위상 정렬 결과는 여러 개 존재할 수 있다.
- 사이클이 없어도 무방향 그래프에는 선행 관계가 없으므로 적용할 수 없고, 방향 그래프에만 적용된다.
오류나 개정된 내용이 보이면 알려주세요