[CLSR] 22.3 Depth-first search(DFS) (Ch 22. Elementary Graph Algorithms)

지금 있는 자리에서 가능하다면 계속 깊게 파고 내려가는 것이 DFS

정점 $v$가 아직 탐색하지 않은 간선을 남겨두고 있다면 남은 간선을 전부 탐색해야 한다.

$v$의 모든 간선을 탐색한 후에는 "backtrack"해서 다른 간선을 탐색하러 이동한다.

이 과정을 소스 정점에서 도달 가능한 모든 정점을 확인할 때까지 반복한다.

만약 탐색하지 못한 정점이 남아있다면 DFS는 그 중 하나를 골라서 새로운 소스로 삼고 과정을 다시 반복한다.

 

BFS와 마찬가지로 이미 발견한 정점 $u$의 인접 리스트를 탐색하는 과정에서 정점 $v$를 발견하면 $v$의 직전 노드 속성인 $v. \pi$를 $u$로 기록한다.

 

BFS의 predecessor 서브그래프가 트리를 형성하는 것과 다르게 DFS의 predecessor 서브그래프는 여러 트리로 이루어져있을 수 있다. 이는 탐색이 여러 소스로부터 반복될 수 있기 때문이다. 따라서 DFS의 predecessor subgraph는 BFS와 조금 다르게 정의한다.

$G_{\pi} = (V , E_{\pi})$를 정의하고 $E_{\pi} = \{ (v. \pi , v) : v \in V \,and\,\, v. \pi \ne NIL \} $라 정의한다.

DFS의 predecessor 서브그래프는 여러 개의 depth-first tree들로 이루어진 depth-first forest를 형성한다. $E_{\pi}$에 있는 간선들은 tree edges라 한다.

 

BFS와 마찬가지로 흰색, 회색, 검정색 세 가지 색으로 간선을 칠할 수 있다.

처음에는 흰색, 처음 방문했을 때는 회색, 인접 리스트가 전부 탐색되면 검은색으로 칠한다. 이렇게 하면 모든 정점이 딱 하나의 depth-first tree에만 속하게 돼서 트리끼리 교차하는 일이 생기지 않는다.

 

또한 DFS는 각 정점에 timestamps를 찍는다. 첫번째 타임스탬프 $v.d$는 $v$를 처음 발견(discover)했을 때(회색일 때) 찍고, 두번째 타임스탬프 $v.f$는 $v$의 인접 리스트 탐색을 모두 마쳤을 때(검정색으로 칠했을 때) 찍는다. 타임스탬프를 통해 그래프의 구조에 대한 정보를 얻고 DFS 과정에 대해 추론해볼 수 있다.

밑에 작성하는 과정은 이와 같은 기록 과정을 보여준다. 모든 $|V|$개의 정점에 하나의 발견과 하나의 마무리가 있기 때문에 타임스탬프는 $1$과 $2|V|$사이의 정수이다. 모든 정점 $u$에 대해 $u.d < u.f$이다. $u$는 시점 $u.d$이전에는 WHITE이고 $u.d$와 $u.f$ 사이에는 GRAY이고, 그 이후에는 BLACK이다.

---

다음 수도코드는 기본적인 dfs 알고리즘을 보여준다. 입력 그래프 $G$는 undirected거나 directed다. 변수 'time'은 타임스탬프를 위한 전역변수이다.

• $DFS(G)$

for each vertex u ∈ G.V
    u.color = WHITE
    u.π = NIL
time = 0
for each vertex u ∈ G.V
    if u.color == WHITE
        DFS-VISIT(G,u)

• $DFS-VISIT(G, u)$

time = time + 1	                // white vertex u has just been discovered
u.d = time
u.color = GRAY
for each v ∈ G.Adj[u]          // explore edge (u, v)
    if v.color == WHITE
        v.π = u
        DFS-VISIT(G, v)
u.color = BLACK                 // blacken u; it is finished
time = time + 1
u.f = time

DFS의 탐색 과정을 보여준다. B는 Back edge, C는 Cross edge, F는 Forward edge를 뜻한다. (CLRS p.605)

같은 깊이에서 탐색 순서에 따라 dfs 결과가 달라질 수 있지만 실질적으로 문제를 일으키는 경우는 잘 없다. 따라서 보통은 어느 dfs 결과를 사용해도 근본적으로는 동등한 결과를 가져온다.

 

$DFS$의 첫번째 반복문과 두번째 반복문은 $DFS-VISIT$의 호출을 제외하면 $\Theta(V)$의 시간이 소요된다. $DFS-VISIT$을 호출시키는 정점 $u$는 흰 색이어야 하고 $DFS-VISIT$이 처음 하는 작업이 정점 $u$를 회색으로 칠하는 것이기 때문에 $DFS-VISIT$은 모든 정점 $v \in V$에 대해 정확히 한번씩 호출된다.

$DFS-VISIT(G,V)$이 수행될 때 반복문은 $|Adj[v]|$번 실행된다. $\sum_{v \in V} | Adj[v]| = \Theta(E) $이므로 $DFS-VISIT$의 반복문을 수행하는 총 비용은 $\Theta(E)$이다. 따라서 DFS의 총 소요시간은 $\Theta(V + E)$이다.

---

DFS의 특성

predecessor 서브그래프 $G_{\pi}$가 실제로 트리들의 숲을 형성한다는 특징. 이는 결국 $u = v. \pi $는 $u$의 인접 리스트를 탐색하는 과정에서 $DFS-VISIT(G, v)$가 호출된 것과 동치임을 의미한다.

또한 정점 $v$가 $u$의 자손이라는 것은 $v$가 발견될 때 $u$는 회색이었다는 말과 동치다.

 

discovery와 finishing time이 괄호 구조(parenthesis structrue)를 보인다는 점이다.

이는 다음의 정리로 나타낼 수 있다.

Theorem 22.7 (Parenthesis theorem)

directed 또는 undirected 그래프 $G = (V, E)$의 DFS에서 임의의 두 정점 $u$와 $v$에 대해 다음 세 조건 중 한 가지가 만족된다.

• $[u.d, u.f]$와 $[v.d,v.f]$의 인터벌은 전혀 겹치지 않고 $u$와 $v$가 depth-first 숲에서 서로의 자손이 아니다.
• $[u.d,u.f]$가 온전히 $[v.d,v.f]$에 담겨지고 $u$가 depth-first 트리에서 $v$의 자손이다.
• $[v.d,v.f]$가 온전히 $[u.d,u.f]$에 담겨지고 $v$가 depth-first 트리에서 $u$의 자손이다.

Proof

$u.d <v.d$인 케이스부터 살펴보자. 여기서 $v.d < u.f$인 서브케이스와 그렇지 않은 서브케이스로 나눠 볼 것이다. 첫번째 서브케이스는 $v.d < u.f$이므로 $u$가 아직 회색일 때 $v$가 발견되었다고 할 수 있다. 따라서 $v$는 $u$의 자손이다. 거기에다 $v$가 $u$보다 더 늦게 발견되었기 때문에 $v$에서 뻗어나간 간선을 모두 탐색하고 $v$가 finish되는 것은 $u$로 돌아가서 finish하는 것보다 먼저 일어난다. 이 경우에는 인터벌 $[v.d,v.f]$는 인터벌 $[u.d,u.f]$에 온전히 담긴다. 두번째 서브케이스는 $u.f < v.d$인 경우이고 $u.d <u.f$가 모든 정점에 성립하므로 $u.d<u.f<v.d<v.f$로 나타낼 수 있다. 따라서 $[u.d, u.f]$와 $[v.d,v.f]$는 교차하지 않는다. 인터벌이 교차하지 않으므로 어떤 정점도 다른 한 정점이 회색일 때 발견되지 않았고 따라서 한 정점이 다른 한 정점의 자손이라 할 수 없다.

$v.d <u.d$인 경우도 비슷하게 확인해볼 수 있다.

 

Corollary 22.8 (Nesting of descendants' intervals)

정점 $v$가 그래프 $G$에 대한 depth-first forest에서 정점 $u$의 적합한 자손인 것은 $u.d <v.d <v.f< u.f$인 것과 동일하다.

Proof Theorem 22.7과 동일하다.

 

다음 정리는 depth-first forest에서 한 정점이 다른 한 정점의 자손일 때 중요한 특성을 보여준다.

Theorem 22.9 (White-path theorem)

그래프 $G = (V,E)$의 depth-first forest에서 정점 $v$가 정점 $u$의 자손인 것은 탐색 과정에서 $u$를 발견했을 당시($u.d$)에 흰색 정점들로만 이루어진 $u$에서 $v$로 가는 경로가 존재한다는 것과 동치이다.

Proof

$\Rightarrow$ : $v = u$인 경우에 $u$에서 $v$로 가는 경로는 정점 $u$만 가지고 있다. $u.d$를 찍는 시점에 이는 여전히 흰 색이다. 이번에는 $v$가 depth-first forest에서 $u$의 적합한 자손이라고 가정하자. 따름정리 22.8에 의해 $u.d < v.d$이므로 $v$는 $u.d$시점에서 흰 색이다. $v$는 $u$의 어느 자손도 될 수 있기 때문에 $u.d$시점에서 $u$에서 $v$로 가는 depth-first forest의 모든 유일한 단순 경로 상의 정점들은 흰색이다.

$\Leftarrow$ : $u.d$ 시점에 정점 $u$에서 $v$로 가는 흰 색 정점들의 경로가 있지만 $v$는 depth-first tree에서 $u$의 자손이 아니라고 가정하자. 또 일반성을 잃지 않고 $v$를 제외한 경로 상의 모든 정점이 $u$의 자손이라고 해보자(그렇게 하고 싶지 않다면 대신 $v$가 경로 상의 $u$의 자손이 되지 않는 정점 중 $u$에 가장 가까운 정점이라고 해보자). $w$를 경로 상에서 $v$의 직전에 있는 정점이라고 하면 $w$는 $u$의 자손이다(물론 $w$가 $u$일 수도 있다.). 따름정리 22.8에 의해 $w.f \leq u.f$이다. $v$는 $u$가 발견된 이후, $w$가 finish된 이후에 발견되어야 하므로 $u.d < v.d < w.f \leq u.f$라 할 수 있다. Thorem 22.7은 인터벌 $[v.d , v.f]$가 인터벌 $[u.d, u.f]$에 온전히 담겨져야 함을 의미하고, 따름정리 22.8에 의해 $v$는 $u$의 자손이어야 할 수 밖에 없다.

---

Classification of edges

dfs는 그 자체로 입력 그래프 $G = (V,E)#의 간선들을 구분할 수 있는 탐색이 될 수 있다.

각 간선의 유형은 그 자체로 그래프에 대한 유용한 정보를 제공할 수 있다. 예를 들어 lemma 22.11에서는 directed graph에서 back edge가 나오지 않는 dfs는 비순환적임을 보여준다.

그래프 $G$의 DFS에서 생성되는 depth-first forest $G_{\pi}$와 연관지어서 네 가지 종류의 간선을 정의할 수 있다.

1. Tree edges는 depth-first forest $G_{\pi}$의 간선들이다. $v$가 $(u,v)$를 탐색하는 과정에서 발견되었다면 간선 $(u,v)$를 트리 간선이라고 부른다.
2. Back edges는 depth-first 트리에서 정점 $u$를 조상인 $v$에게 연결하는 간선 $(u,v)$이다. directed 그래프에서 self-loop도 back edge로 본다.
3. Forward edges는 depth-first forest의 간선 $(u,v)$이 정점 $u$를 자손인 $v$로 잇지만 트리 간선은 아닌 것이다.
4. Cross edges는 위를 제외한 나머지 모든 간선이다. 동일한 depth-first tree에서 한 정점이 다른 한 정점의 조상이 아닌 이상 둘을 이을 수도 있고, 다른 depth-first tree의 정점을 연결하는 간선일 수도 있다. 

간선 $(u,v)$를 탐색할 때 정점 $v$의 색을 통해 어떤 종류의 간선인지 확인할 수 있다.

1. WHITE는 트리 간선임을 의미한다.
2. GRAY는 역방향 간선(back edge)임을 의미한다.
3. BLACK은 순방향 간선(forward edge) 또는 교차 간선(cross edge)임을 의미한다($u.d < v.d$이면 순방향 간선, $u.d > v.d$이면 교차 간선).

undirected 그래프는 $(u,v)$와 $(v,u)$가 동일하기 때문에 간선을 구분함에 있어서 모호함이 있을 수 있다. 그런 경우에는 분류된 유형 중에서 처음으로 분류된 유형으로 분류한다.

다음은 undirected graph의 dfs에서 순방향 간선과 교차 간선이 나오지 않음을 보여준다.

Theorem 22.10

undirected 그래프 $G$의 DFS에서 $G$의 모든 간선은 트리 간선 또는 역방향 간선이다.

Proof

$(u,v)$를 $G$의 임의의 간선이라고 하자. 또한 일반성을 잃지 않고 $u.d < v.d$라고 하자. 그러면 $v$는 $u$의 인접 리스트에 있으므로 탐색은 $u$를 finish하기 전에 $v$를 discover하고 finish해야 한다($u$가 회색일 동안). 간선 $(u,v)$를 처음 탐색하는 시점에 $u$에서 $v$로 향하는 방향이면, 그 시점 전까지 $v$는 발견되지 않았을 것이다. $v$가 이미 발견되었다고 하면 이는 이미 $v$에서 $u$방향으로 탐색할 때 발견된 경우이므로 $(u,v)$를 처음 탐색하는 것이 아니게 된다. 그러므로 $(u,v)$는 트리 간선이다. 만약 탐색 과정에서 $(u,v)$를 $v$에서 $u$로 가는 방향에서 처음 탐색했다면 $u$는 $u$의 발견 시점에서 회색으로 칠해졌으므로 $(u,v)$의 탐색 시점에 $u$는 회색이다. 따라서 $(u,v)$는 역방향 간선이다.