[자료구조] 그래프(Graph) 순회

그래프 순회(graph traversal), 그래프 탐색(graph search)

 - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산

 - 그래프 탐색 방법

    ㄴ 깊이 우선 탐색 (Depth First Search : DFS)

    ㄴ 너비 우선 탐색 (Breadth First Search : BFS)

깊이 우선 탐색(Depth First Search : DFS) >>> A - B - D - G - E - C - F

① 시작 정점 v를 결정하여 방문
② 정점 v에 인접한 정점 중
    1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행
    2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시 ②과정 반복 수행
③ 스택이 공백이 될 때까지 ②반복 수행

---

너비 우선 탐색 (Breadth First Search : BFS) >>> A - B - C - D - E - G - F

① 시작 정점 v를 결정하여 방문
② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue
③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복
④ 큐가 공백이 될 때까지 ②~③반복