그래프를 구성하는 모든 꼭짓점(Vertex)들을 체계적으로 방문하여 탐색하는 자료 검색 방법.

일반적으로 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 두 종류가 많이 사용된다.

(전위 운행법, 중위 운행법, 후위 운행법 등은 이 글에서는 생략한다.)

DFS (Depth First Search)

한 노드를 시작으로 인접한 다른 노드를 탐색하기를 반복하여 끝까지 탐색하면 다시 상위 레벨의 다른 노드에서 탐색을 이어가며 모든 Vertex를 방문한다.

• '깊이 우선 탐색'이라는 말 그대로 깊은 곳으로 우선 탐색을 진행하는 방식.

• First In Last Out 방식의 Stack과 중복 처리를 방지하기 위해 이미 접근했던 Vertex를 저장하는 방식을 활용한다.

[예시 1]

• 깊이 우선 탐색

1. 탐색 시작점 A를 stack과 seen에 각각 저장

   stack = [A], seen = {A}

2. 탐색을 마친 A는 stack에서 제거 후 A와 인접하는 vertex들 B, C, D를 stack과 seen에 각각 저장

   stack = [D, C, B], seen = {A, B, C, D}

3. stack에 마지막으로 저장된 B를 탐색 후 제거하며 B와 인접하는 A, C, E 중 seen에 속하지 않은 E를 stack과 seen에 각각 저장

   stack = [D, C, E], seen = {A, B, C, D, E}

4. stack에 마지막으로 저장된 E를 탐색 후 제거하며 E와 인접하는 B, G 중 seen에 속하지 않은 G를 stack과 seen에 각각 저장

   stack = [D, C, G], seen = {A, B, C, D, E, G}

5. stack에 마지막으로 저장된 G를 탐색 후 제거하고 G와 인접하는 E는 이미 seen에 저장되어 있으므로 따로 처리하지 않음

   stack = [D, C], seen = {A, B, C, D, E, G}

6. stack에 마지막으로 저장되어 있는 C를 탐색 후 제거하며 C와 인접하는 A, B, D, F 중 seen에 속하지 않은 F를 stack과 seen에 각각 저장

   stack = [D, F], seen = {A, B, C, D, E, F, G}

7. stack에 마지막으로 저장된 F를 탐색 후 제거하고 F와 인접하는 C, D는 이미 seen에 저장되어 있으므로 따로 처리하지 않음

   stack = [D], seen = {A, B, C, D, E, F, G}

8. stack에 마지막으로 저장된 D를 탐색 후 제거하고 D와 인접하는 A, C, F는 이미 seen에 저장되어 있으므로 따로 처리하지 않음

   stack = [], seen = {A, B, C, D, E, F, G}

9. stack에 남은 것이 없으므로 탐색 종료.

• [예시 1]의 그래프 깊이 우선 탐색 처리 순서: A, B, E, G, C, F, D

BFS (Breadth First Search)

한 노드를 시작으로 인접한 다른 노드를 탐색하기를 반복하여 같은 레벨의 노드 탐색이 끝나면 하위 레벨의 다른 노드에서 탐색을 이어가며 모든 Vertex를 방문한다.

• '너비 우선 탐색'이라는 말 그대로 옆으로 우선 탐색을 진행하는 방식.

• First In First Out 방식의 Queue와 중복 처리를 방지하기 위해 이미 접근했던 Vertex를 저장하는 방식을 활용한다.

[예시 2]

• 너비 우선 탐색

1. 탐색 시작점 A를 queue와 seen에 각각 저장

   queue = [A], seen = {A}

2. A의 탐색을 마치고 queue에서 제거 후 인접한 vertex들 B, C, D를 queue와 seen에 각각 저장

   queue = [B, C, D], seen = {A, B, C, D}

3. queue의 맨 처음 값인 B를 탐색 후 제거하며 인접한 A, C, E 중 seen에 속하지 않은 E를 queue와 seen에 각각 저장

   queue = [C, D, E], seen = {A, B, C, D, E}

4. queue의 맨 처음 값인 C를 탐색 후 제거하며 인접한 A, B, D, F 중 seen에 속하지 않은 F를 queue와 seen에 각각 저장

   queue = [D, E, F], seen = {A, B, C, D, E, F}

5. queue의 맨 처음 값인 D를 탐색 후 제거하며 인접한 A, C, F는 이미 seen에 속해 있으므로 따로 처리하지 않음

   queue = [E, F], seen = {A, B, C, D, E, F}

6. queue의 맨 처음 값인 E를 탐색 후 제거하며 인접한 B, G 중 seen에 속하지 않은 G를 queue와 seen에 각각 저장

   queue = [F, G], seen = {A, B, C, D, E, F, G}

7. queue의 맨 처음 값인 F를 탐색 후 제거하며 인접한 C, D는 이미 seen에 속해 있으므로 따로 처리하지 않음

   queue = [G], seen = {A, B, C, D, E, F, G}

8. queue의 맨 처음 값인 G를 탐색 후 제거하며 인접한 E는 이미 seen에 속해 있으므로 따로 처리하지 않음

   queue = [], seen = {A, B, C, D, E, F, G}

9. queue에 남은 것이 없으므로 탐색 종료.

• [예시 1]의 그래프 너비 우선 탐색 처리 순서: A, B, C, D, E, F, G