다음 인접 리스트(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가 없으므로 성립하지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기