다음 인접 리스트(adjacency list)로 표현된 그래프에서 깊이… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
다음 인접 리스트(adjacency list)로 표현된 그래프에서 깊이 우선 탐색(DFS: Depth First Search)으로 순회하고자 한다. 정점(vertex) 0부터 시작한 순회 순서는?
1
0, 1, 2, 3, 4, 5, 6
2
0, 1, 3, 2, 4, 6, 5
3
0, 1, 3, 2, 5, 6, 4
4
0, 1, 3, 2, 5, 4, 6
해설
정점 0에서 시작한 깊이 우선 탐색의 순회 순서는 0, 1, 3, 2, 5, 6, 4이다.
DFS는 현재 정점의 인접 리스트를 앞에서부터 보며 아직 방문하지 않은 정점으로 곧바로 내려간다.
0의 리스트에서 1 → 1의 리스트에서 3(0은 방문함) → 3의 리스트에서 2 → 2의 리스트에서 5 → 5의 리스트에서 6 → 6의 리스트에서 4 순으로 방문한다.
- 0, 1, 2, 3, 4, 5, 6은 가까운 정점부터 넓게 방문하는 너비 우선 탐색의 순서이다.
- 2 다음에 4를 방문하는 순서는 2의 인접 리스트에 4가 없으므로 성립하지 않는다.
- 5 다음에 4를 방문하는 순서는 5의 인접 리스트(2, 6)에 4가 없으므로 성립하지 않는다.
오류나 개정된 내용이 보이면 알려주세요
