[알고리즘] 그래프 순회, 탐색

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

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

그래프 탐색방법

v깊이 우선 탐색(depth first search : DFS)

§순회 방법

①시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색

②더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴

③다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문

•가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서
다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 

v너비 우선 탐색(breadth first search : BFS)

§순회 방법

•시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

•가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는
순회방법

•인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 큐를 사용