그래프 알고리즘 - (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 사용