다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 … | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 13년 1회차
다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 것이다. 이에 대한 위상 정렬(topological sorting)의 결과로 옳은 것은? (단, 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑된다)
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f |
1
a, b, c, d, e, f
2
a, b, c, e, d, f
3
a, c, b, e, d, f
4
a, c, e, b, d, f
해설
위상 정렬 결과는 a, b, c, e, d, f이다.
간선은 a→b, a→c, b→c, b→d, c→d, c→e, d→f, e→d, e→f이다. 진입차수가 0인 노드를 차례로 꺼내면 a → b → c → e → d → f로 순서가 하나로 정해진다.
- a, b, c, d, e, f: e→d 간선이 있어 d가 e보다 앞설 수 없다.
- a, c, b, e, d, f: b→c 간선이 있어 c가 b보다 앞설 수 없다.
- a, c, e, b, d, f: 역시 c가 b보다 먼저 나와 b→c 간선을 어긴다.
오류나 개정된 내용이 보이면 알려주세요