위상 정렬(topological sort)이 가능한 그래프만을 모두 고… | [9급 지방직 컴퓨터일반] 25년 1회차 기출문제 상세 페이지

위상 정렬이 가능한 그래프는 ㄱ과 ㄹ이다.
위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능하다. ㄱ은 A, B, D, C 순으로, ㄹ은 A, B, C, D, E, F, G 순으로 모든 간선이 앞에서 뒤로 향하게 나열할 수 있다.
ㄱ, ㄴ: ㄴ은 간선에 방향이 없는 무방향 그래프라 선후 관계를 정할 수 없으므로 위상 정렬 대상이 아니다.
ㄴ, ㄷ: ㄴ은 무방향 그래프이고, ㄷ은 A → B → C → A로 되돌아오는 사이클이 있어 둘 다 불가능하다.
ㄷ, ㄹ: ㄷ에는 A → B → C → A와 C → E → F → C의 사이클이 있어 위상 정렬이 불가능하다.