다음은 방향그래프를 인접 리스트로 표현한 것이다. 이 그래프에 대한 설… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
다음은 방향그래프를 인접 리스트로 표현한 것이다. 이 그래프에 대한 설명으로 옳지 않은 것은?
| 정점 | 인접 리스트 |
|---|---|
| 0 | [1 | 50] → [2 | 45] → [3 | 10 | NULL] |
| 1 | [2 | 10] → [3 | 15 | NULL] |
| 2 | [4 | 30 | NULL] |
| 3 | [0 | 20] → [4 | 15 | NULL] |
| 4 | [1 | 20] → [2 | 35 | NULL] |
| 5 | [4 | 3 | NULL] |
1
모든 사이클 경로는 (0,3,0), (2,4,2), (0,1,3,0), (1,2,4,1), (1,3,4,1), (0,2,4,1,3,0)이고, 그 경로에 각각 대응하는 길이는 2, 2, 3, 3, 3, 5이다.
2
각 정점(0,1,2,3,4,5)에 각각 대응되는 진입차수는 1, 2, 3, 2, 3, 0이다.
3
각 정점(0,1,2,3,4,5)에 각각 대응되는 인접한 정점의 집합은 {1,2}, {2,3}, {4}, {0,4}, {1,2}, {4,2}이다.4
각 정점(0,1,2,3,4,5)에서 각각 대응되는 진출차수는 3, 2, 1, 2, 2, 1이다.
해설
옳지 않은 것은 인접한 정점의 집합에 대한 설명이다.
리스트를 간선으로 옮기면 0→1, 0→2, 0→3, 1→2, 1→3, 2→4, 3→0, 3→4, 4→1, 4→2, 5→4이다. 따라서 정점 0의 인접 정점은 {1, 2, 3}, 정점 5의 인접 정점은 {4}뿐인데 각각 {1, 2}, {4, 2}로 잘못 적었다.
- 사이클 경로 설명: 3→0 으로 돌아오는 사이클 3개와 0을 지나지 않는 사이클 3개가 제시된 6개와 정확히 일치하고, 길이(간선 수)도 2, 2, 3, 3, 3, 5로 맞다.
- 진입차수 설명: 각 정점으로 들어오는 간선 수가 1, 2, 3, 2, 3, 0으로 맞다.
- 진출차수 설명: 각 리스트의 노드 수가 3, 2, 1, 2, 2, 1로 맞다.
오류나 개정된 내용이 보이면 알려주세요