그래프 탐색

들어가며..

그래프 이론에서의 가장 기본적인 부분으로, 많은 그래프 알고리즘에는 그래프 탐색이 이용된다. 본문에서는 BFS와 DFS에 대해 다룬다.

 

그래프 탐색의 시간복잡도

  그래프 탐색은 말 그대로 그래프를 탐색하는 것이다. 모든 정점과 간선을 확인해야 한다. 따라서 어떤 방법으로 탐색을 하던 간에 알고리즘의 시간복잡도는 \(\Omega(|V+E|)\)이다. 그리고 본문에서 다루게될 DFS와 BFS는 인접 리스트를 이용할 때 \(\Theta(|V+E|)\)의 시간복잡도를 가진다.

 

DFS

  DFS(depth first search, 깊이 우선 탐색)은 현재 방문할 수 있는 vertex 중에서 depth가 큰 vertex부터 방문하는 방법이다. 다만, 이는 검색 트리에서의 이야기이고 본문에서 다룰 그래프에서의 탐색과는 거리가 있다. 일반적인 그래프에서는 depth를 정의하기 힘들다. 그래프에서의 DFS를 그래프의 vertex에 depth를 달아주겠다. 이는 DFS를 수행하는 과정에 따라 달라지는 것으로, 탐색을 해 나감에 따라 매진다. 즉, '현재 vertex의 depth = 이전 탐색한 vertex의 depth+1'로 정의할 수 있다. 이렇게 정의하면, DFS는 인터넷에서 찾아볼 수 있는 gif와 같은 형식의 탐색을 하게 될 것이다.

 

BFS

  BFS(breadth first search, 너비 우선 탐색)은 시작 vertex에 인접한 vertex부터 우선적으로 탐색하는 방법이다. 이는 '현재 방문할 수 있는 vertex 중에서 depth가 가장 작은 vertex부터 방문하는 방법'과 동치이다. 이때 그래프의 depth는 DFS를 설명할 때 이용했던 정의와 같다. BFS를 이용하면 가중치가 없는 그래프에서 최단 경로를 찾을 수 있다. 또한, Dijkstra's algorithm, Bellman-Ford algorithm, shortest path faster algorithm 등의 단일 출발지 최단 경로 알고리즘(single source shortest path algorithm)들은 모드 BFS 기반이다.