10장 그래프 순회

그래프 순회

- 하나의 정점에서 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다.

- 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다.

1. 깊이 우선 탐색

깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 함으로써 모든 정점을 방문하는 쉰회 방법이다. 스택을 사용한다.

 

(1) 시작 정점 v를 결정하여 방문한다. (2) 정점 v에 인접한 정점 중에서     ⓐ 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 설정하고 (2) 반복.     ⓑ 방문하지 않은 정점이 없으면 스택을 pop하여 구한 가장 마지막 방문 정점을 v로 설정하고 다시 (2) 수행한다. (3) 스택이 공백이 될 때까지 (2)를 반복한다.

1. 초기세팅 후 정점 A 탐색 시작

 

 

2. A에 방문하지 않은 정점 B,C가 있으므로 A를 스택에 push하고, 인접 정점 B와 C중 오름차순에 따라 B를 탐색한다.

 

3. G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push하고, 인접 정점 E와 F중에서 오름차순에 따라 E를 탐색한다. (같은방법으로 쭉 탐색)

 

4. E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push하고, 인접 정점 C를 선택하여 탐색을 계속한다.

 

5. C에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 E에 대해서 방문하지 않은 인접 정점이 있는지 확인한다.(룰에 따라 push pop 하여 탐색)

 

 

 

6. 최종 깊이 우선 탐색 순회 경로

 

2. 너비 우선 탐색

너비 우선 탐색은 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법으로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회  방법이다. 큐를 사용한다.

 

(1) 시작 정점 v를 결정하여 방문한다. (2) 정점 v에 인접한 정점 중에서     ⓐ 방문하지 않은 정점이 있으면 차례로 방문하면서 큐에 enQueue한다.     ⓑ 방문하지 않은 정점이 없으면 큐를 deQueue하여 구한 정점을 v로 설정하고 (2) 반복한다. (3) 큐가 공백이 될 때까지 (2)를 반복한다.

1. 초기세팅 후 정점 A 탐색 시작

2. A에 방문하지 않은 모든 인접 정점 B, C를 방문하고 큐에 enQueue한다.

3. 정점 A에 대한 인접 정점들을 처리했으므로 다음 정점을 찾기 위해 B를 deQueue한다.

4. 정점 B에서 방문하지 않은 모든 인접 정점 D, E를 방문하고 큐에 enQueue한다.(룰에 따라 탐색 마무리한다.)

5. 최종 너비 우선 탐색 경로