다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색(Depth… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색(Depth First Search)을 수행할 경우 나타날 수 없는 순서는?
1
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
2
1 - 2 - 3 - 4 - 6 - 7 - 5 - 8
3
1 - 2 - 3 - 4 - 6 - 5 - 7 - 8
4
1 - 2 - 3 - 4 - 5 - 7 - 8 - 6
해설
1-2-3-4-5-6-7-8은 깊이 우선 탐색으로 나올 수 없다.
깊이 우선 탐색은 현재 정점에 방문하지 않은 인접 정점이 남아 있으면 반드시 그쪽으로 내려가고, 없을 때만 되돌아간다. 정점 5는 7, 8과 인접하고 6과는 연결되지 않으므로, 5 다음에는 7이나 8이 와야 한다.
- 1-2-3-4-6-7-5-8: 6에서 막혀 4로 돌아가 7을 방문하고, 7에서 5, 5에서 8로 가는 정상 순서이다.
- 1-2-3-4-6-5-7-8: 6에서 4로 되돌아가 5, 5에서 7, 다시 5로 돌아가 8을 방문한다.
- 1-2-3-4-5-7-8-6: 5에서 7, 막혀 5로 돌아가 8, 다시 4로 돌아가 6을 방문한다.
오류나 개정된 내용이 보이면 알려주세요
