시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: D… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: Depth First Search)의 방문 순서는? (단, 인접한 정점들은 오름차순으로 방문한다)
1
6, 5, 3, 1, 0, 2, 4, 7, 8, 9
2
6, 5, 7, 3, 8, 9, 1, 4, 0, 2
3
6, 5, 3, 4, 2, 1, 0, 7, 8, 9
4
6, 5, 7, 3, 1, 4, 0, 2, 8, 9
해설
정점 6에서 인접 정점을 오름차순으로 방문하는 DFS의 방문 순서는 6, 5, 3, 1, 0, 2, 4, 7, 8, 9이다.
6의 인접 정점(5, 7) 중 작은 5로 가고, 5에서 3, 3에서 1, 1에서 0으로 내려간다. 0은 더 갈 곳이 없어 되돌아가(backtracking) 1의 다음 인접 정점 2, 이어서 4를 방문한다.
4의 인접 정점은 모두 방문했으므로 5까지 되돌아가 7을 방문하고, 7에서 8, 9 순으로 방문하면 탐색이 끝난다.
- 6, 5, 7, 3, 8, 9, 1, 4, 0, 2: 시작 정점에서 가까운 정점부터 차례로 방문한 너비 우선 탐색(BFS)의 순서이다.
- 6, 5, 3, 4, 2, 1, 0, 7, 8, 9: 3의 인접 정점 중 1이 4보다 작으므로 1을 먼저 방문해야 한다.
- 6, 5, 7, 3, 1, 4, 0, 2, 8, 9: 5에서 3이 7보다 작은데 7을 먼저 방문해 오름차순 조건에 어긋난다.
오류나 개정된 내용이 보이면 알려주세요
