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

G6보다 G8이 먼저 나오는 순서는 위상 순서가 될 수 없다. 그림에 G6→G8 간선이 있기 때문이다.
간선은 G1→G2, G1→G3, G1→G4, G2→G5, G2→G6, G2→G8, G3→G6, G4→G6, G4→G7, G5→G8, G6→G8이다. 위상 순서에서는 모든 간선의 시작 정점이 끝 정점보다 앞에 있어야 하며, G8은 G2, G5, G6가 모두 나온 뒤에야 올 수 있다.
G1, G2, G3, G4, G5, G6, G7, G8: 모든 간선의 선후 관계를 만족한다.
G1, G3, G2, G4, G6, G5, G8, G7: G6 앞에 G2·G3·G4가, G8 앞에 G2·G5·G6가 모두 있어 유효하다.
G1, G4, G3, G2, G7, G6, G5, G8: G7은 G4 뒤, G6는 G2·G3·G4 뒤, G8은 마지막이라 유효하다.