다음 인접 행렬(adjacency matrix)로 표현된 그래프에 대해… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 인접 행렬(adjacency matrix)로 표현된 그래프에 대해 위상 정렬(topological sort)을 수행한 후, 위상 순서(topological order)에서 마지막에 위치하는 정점은? (단, 위상 정렬 과정에서 선택 가능한 정점이 여러 개인 경우 가장 작은 숫자의 정점을 선택한다)
| 시작 정점 ＼ 도착 정점 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | |||||
| 1 | 1 | |||||||
| 2 | ||||||||
| 3 | 1 | |||||||
| 4 | 1 | 1 | 1 | |||||
| 5 | 1 | |||||||
| 6 | 1 | 1 | ||||||
| 7 | 1 |
1
1
2
2
3
3
4
6
해설
위상 순서의 마지막 정점은 2이다.
진입 차수가 0인 정점을 고르고 그 진출 간선을 지우는 과정을 반복한다. 처음 진입 차수가 0인 정점은 4뿐이며, 전체 순서는 4 → 0 → 5 → 6 → 7 → 3 → 1 → 2이다.
- 4 제거 → 0, 5의 진입 차수가 0 → 작은 0 선택
- 0 제거 → 후보는 5뿐 → 5 제거 후 6의 진입 차수가 0
- 6 제거 → 7 선택, 7 제거 후 3의 진입 차수가 0
- 3 제거 → 1 선택, 1 제거 후 2 선택
정점 2는 1과 4에서 들어오는 간선만 있고 나가는 간선이 없어 가장 늦게 남는다. 1·3·6은 모두 2보다 앞서 선택된다.
오류나 개정된 내용이 보이면 알려주세요