다음 그래프의 위상 정렬(topological sorting) 결과로 … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
다음 그래프의 위상 정렬(topological sorting) 결과로 나올 수 있는 위상 순서(topological order)로 옳지 않은 것은?
1
A, B, C, D, E, F
2
C, A, B, E, D, F
3
A, C, B, E, D, F
4
C, A, D, B, E, F
해설
위상 순서로 옳지 않은 것은 C, A, D, B, E, F이다.
그래프의 간선은 A→B, B→D, B→E, B→F, C→D, C→E, E→F이다. 위상 순서는 모든 간선 u→v에 대해 u가 v보다 앞서야 하는데, 이 순서는 B→D 간선이 있음에도 D가 B보다 먼저 나온다.
- A, B, C, D, E, F: 모든 간선의 선후 관계를 만족한다.
- C, A, B, E, D, F: 진입 차수가 0인 C, A가 먼저 오고 B 다음에 E, D, 마지막에 F가 와 모든 조건을 만족한다.
- A, C, B, E, D, F: A→B, C→D, C→E, B→D, B→E, E→F 조건을 모두 만족한다.
오류나 개정된 내용이 보이면 알려주세요
