그래프 알고리즘 - (2) 넓이 우선 탐색 & 깊이 우선 탐색 BFS & DFS
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.
1. DFS
DFS는 어떤 vertex s로부터 reachable한 vertex를 뽑아내는 과정이다.
요점은 아래 2가지이다.
- visited인 vertex는 다시 가지 않는다
- 현재 explore 중인 vertex와 연결된 vertex를 바로 탐색한다
pseudo code
procedure DFS(G)
for all vertex v in V do
visited[v] = false
end for
for visited[v] == false do
explore(v)
end for
procedure explore(w)
visited[w] = true
for each edge (w, u) in E do
if visited[u] == false then
explore(u)
end if
end for
DFS의 correctness 증명
Q. v로부터 reachable한 모든 vertex를 찾아낼 수 있는가?
가능하다. 어떤 vertex u, v가 있고 v에서 u가 reachable이라 두고, 그 path를 π라 두자.
이 때 proof by contradiction으로 v에서 u는 reachable이지만 찾지 못한다고 가정하자. 그러면 π에서 찾지 못한 vertex w, explore에서 마지막으로 찾은 vertex z라고 두자. z 다음이 w기 때문에 explore(z)를 하면 w를 찾을 수 있고, 따라서 가정에 모순이다. 따라서 참.
Q. 모든 vertex v가 v로부터 reachable한가?
자명하다. DFS의 과정을 역으로 살펴보면 v로 도달하기 때문이다.
Time Complexity of DFS
모든 vertex를 방문하므로 O(|V|). 그리고 edge (u, v)를 explore(u), explore(v)에서 2번씩 탐색하므로 O(2|E|). 따라서 O(|V| + |E|)이다.
2. BFS
BFS는 어떤 vertex s로부터 queue를 이용해 reachable한 vertex를 뽑아내는 과정이며, layer by layer로 탐색하는 기법이다.
$L_{i}$를 $L_{0}$부터 $L_{i-1}$에 없으면서 $L_{i-1}$에서 1번의 탐색으로 도달한 vertex의 집합이라고 표현할 수 있다. 따라서 또한 s로부터 $L_{i}$까지의 길이는 무조건 i이며, shortest path 또한 length i이다.
요점은 아래 3가지이다.
- q의 top을 explore한다.
- vertex u를 explore 시, u와 connected이고 unvisited인 모든 vertex를 q에 넣는다.
- q에 넣을 때 visited를 표기한다.
- queue가 빌 때 까지 위 2가지를 반복한다
pseudo code
procedure BFS(G, s)
for all u in V do
dist(u) = INF
end for
dist(s) = 0 // visited 표기
Q = [s] (queue containing s)
while !Q.empty() do
u = Q.pop()
for all edges (u, v) in E do
if dist(v) == INF then
Q.push((u, v)) // visited 표기
dist(v) = dist(u) + 1
end if
end for
end while
Time Complexity of DFS
DFS와 동일하게 모든 vertex를 방문하므로 O(|V|). 그리고 edge (u, v)를 explore(u), explore(v)에서 2번씩 탐색하므로 O(2|E|). 따라서 O(|V| + |E|)이다.
3. DFS vs BFS
DFS | BFS |
더 깊은 방향으로 탐색(deep) | layer by layer로 탐색(broad) |
stack 사용(procedure recursive call) | queue 사용 |