자료구조-그래프 순회(깊이 우선, 너비 우선)

그래프 순회=그래프 탐색: 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산

 

깊이 우선vs너비 우선

 

깊이 우선 탐색

순회 방법

-시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없을 때, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하는 식

-가장 마지막에 만났던 갈림길 간선의 정점으로 돌아가야 하기 때문에 후입선출 구조 스택을 사용한다

 

구현

1. visited라는 방문 체크 배열을 전부 false(하나도 방문하지 않은 상태)로 초기화

2. 스택 생성

3. visited[v]=true; 시작하는 첫번째 위치는 방문했다고 표시

4. 스택이 empty가 아닐 때까지, 현재 노드의 인접 정점w가 false(방문x)라면 일단 스택에 현재 노드v를 세이브 포인트로 집어 넣음. 그리고 인접 정점에 visited[w]=true로 방문 표시를 해주고 방문한다

5. w로 이동했으므로 인접 정점w가 현재 노드v가 된다

6. 인접 정점w가 방문 했다면 스택에서 값을 하나 뺀다

 

순회 과정

 

1. 그래프 G9의 깊이 우선 탐색을 위한 초기 상태: 배열 visited를 false로 초기화하고 공백 스택을 생성한다

 

2. 정점 A를 시작으로 깊이 우선 탐색 시작

 

3. 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push하고, 인접 정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속함

A와 B를 방문했으니 visited도 TRUE가 됨

 

4. B를 와봤더니 정점 B에도 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push하고, 방문하지 않은 인접 정점 D와 E 중에서 오름차순에 따라 D를 선택하여 탐색을 계속

D방문했으니까 visited를 TRUE로

 

5. D에도 방문하지 않은 정점 G가 있으므로 D를 스택에 push하고, 인접 정점 G를 선택하여 탐색을 계속

G방문했으니까 visited를 TRUE로

 

6. 정점 G에 방문하지 않은 정점 E, F가 있으므로(D는 방문함) G를 스택에 push하고, 방문하지 않은 인접 정점 E와 F중에서 오름차순에 따라 E를 선택하여 탐색을 계속

 

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

 

8. 정점 C에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 E에 대해서 방문하지 않은 인접 정점이 있는지 확인. 정점 E는 방문하지 않은 인접 정점이 없음

 

9. 현재 정점 E에서 방문할 수 있는 인접 정점이 없으므로, 다시 스택을 pop하여 받은 정점 G에 대해서 방문하지 않은 인접 정점이 있는지 확인

 

10. 현재 정점 G에서 방문하지 않은 정점 F가 있으므로 G를 스택에 push하고, 인접 정점 F를 선택하여 탐색을 계속

 

11. 현재 정점 F에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 G에 대해서 방문하지 않은 인접 정점이 있는지 확인. 정점 G는 방문하지 않은 인접 정점이 없음

 

12. 현재 정점 G에서 방문하지 않은 인접 정점이 없으므로 다시 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 D에 대해서 방문하지 않은 인접 정점이 있는지 확인. 정점 D는 방문하지 않은 인접 정점이 없음

 

13. 현재 정점 D에서 방문하지 않은 인접 정점이 없으므로 다시 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 B에 대해서 방문하지 않은 인접 정점이 있는지 확인. 정점 B는 방문하지 않은 인접 정점이 없음

 

14. 현재 정점 B에서 방문하지 않은 인접 정점이 없으므로 다시 마지막 정점으로 돌아가기 위해 스택을 pop. 그리고 받은 정점 A에 대해서 방문하지 않은 인접 정점이 있는지 확인. 정점 A는 방문 하지 않은 인접 정점이 없음

15. 현재 정점 A에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop. 스택이 공백이므로 깊이 우선 탐색을 종료

 

최종적으로 A-B-D-G-E-C-F가 된다

 

 

너비 우선 탐색

순회 방법

 

구현

1. visited 전부 0으로 초기화

2. 큐 생성

3. 첫 노드를 방문 했다는 true로 표시

4. 큐가 empty가 아닐 동안, 인접한 노드 중 방문 안 한 false를 찾아서 방문하고 visited를 true로 바꾼다. 방문한 인접 노드를 큐에 넣는다

5. 방문 한 노드면 큐에서 값을 뺀다

 

순회 과정

0. 초기상태 : 배열 visited를 False로 초기화, 공백 큐를 생성

 

1. 정점 A를 시작으로 너비 우선 탐색을 시작

 

2. 정점 A에서 방문하지 않은 모든 인접 정점 B, C를 방문하고 큐에 enQueue(넣음)

B, C를 방문했으니 visited를 True로

 

3. 정점 A에 대한 인접 정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue(뺀다)하여 B를 받음

 

4. 정점 B에서 방문하지 않은 모든 인접 정점 D, E를 방문하고 큐에enQueue

 

5. 정점 B에 대한 인접 정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 C를 받음

 

6. 정점 C에는 방문하지 않은 인접 정점이 없으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 D를 받음

 

7. 정점 D에서 방문하지 않은 인접 정점 G를 방문하고 큐에 enQueue

 

8. 정점 D에 대한 인접 정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 E를 받음

 

9. 정점 E에는 방문하지 않은 인접 정점이 없으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 G를 받음

 

10. 정점 G에서 방문하지 않은 인접 정점 F를 방문하고 큐에 enQueue

 

11. 정점 G에 대한 인접 정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 F를 받음

12. 정점 F는 모든 인접 정점을 방문했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue. 큐가 공백이므로 너비 우선 탐색을 종료

 

최종적으로 A-B-C-D-E-G-F가 된다