다음 그래프에 대해 위상 정렬(topological sort) 알고리즘… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

위상 순서로 옳지 않은 것은 0, 2, 4, 5, 1, 3, 6이다.
위상 순서는 모든 간선 u→v 에 대해 u가 v보다 앞에 와야 한다. 정점 4는 1과 2 모두에서 들어오는 간선을 가지므로 1과 2가 출력된 뒤에야 나올 수 있는데, 이 순서는 1보다 4를 먼저 두어 간선 1→4를 어긴다.
0, 1, 2, 3, 4, 5, 6: 모든 정점이 선행 정점 뒤에 놓여 올바른 위상 순서이다.
0, 1, 3, 2, 4, 5, 6: 3은 1 뒤, 4는 1·2 뒤, 6은 3·4·5 뒤에 있어 올바르다.
0, 2, 5, 1, 3, 4, 6: 5는 2 뒤, 4는 1·2 뒤에 오며 6이 마지막이므로 올바르다.