『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 

본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인 공부 및 복습이 주목적일 뿐, 상업적 의도는 없습니다. 

Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein』

5-1. Depth-First Search

DFS는 가능할 때마다 더 깊게 검색하는 방법이다.

BFS처럼 DFS에서도 이미 검색된 vertex u의 adjacency list를 검색하는 도중 vertex v를 발견하면, v의 predecessor attribute v.π = u 로 둔다.

BFS와 달리 DFS에서는 여러 소스에서 검색이 반복되기 때문에 predecessor subgraph가 tree가 아닌 여러 개의 tree, forest를 형성한다.

즉, DFS의 predecessor subgraph는 아래와 같이 정의된다.

G_π = (V, E_π), 그리고 E_π = {(v.π, v): v ∈ V and v.π != NIL}

이는 depth-first tree들로 구성된 depth-first forest를 형성한다.

DFS에서도 초기 흰색, 검색 중 회색, 검색 후 검정으로 색을 표기한다.

이 외에, DFS는 각 vertex를 timestamp한다. 각 vertex v는 최초 발견하여 회색 변경시 v.d에, 그리고 v의 adjacency list 검색을 끝내 검정 변경시 v.f에 시간을 기록한다.

이 timestamp들은 그래프의 구조에 중요한 정보를 제공한다.

각각의 |V|개 vertices에 대해 하나의 발견 이벤트, 하나의 완료 이벤트가 있기 때문에 timestamp들은 1과 2|V| 사이의 정수이다. 

그리고 모든 vertex u에 대해 u.d < u.f 이다.

아래는 과정을 표현한 것이다.

위에서 B, C, F는 back, cross, forward edges로, 조금 후 설명.

아래는 기본 DFS 알고리즘의 pseudocode이고, input graph G는 directed일수도 undirected일 수도 있다. 변수 time은 timestamping을 위한 전역 변수이다.

DFS의 running time에 대해서는, 우선 DFS 함수의 Line 1-3의 loop과 Line 5-7의 loop은 θ(V)이다.

그리고 DFS-VISIT 함수는 각 vertex v ∈ V가 정확히 한번씩만 실행된다. 한번 실행될 때 회색으로 변하고, 이 함수는 흰색에 대해서만 실행되기 때문이다.

DFS-VISIT에서의 Line 4-7의 loop는 |Adj[v]|번 실행된다. 그리고 ∑_v∈V|Adj[v]| = θ(E) 이므로, loop는 θ(E)다.

따라서 DFS의 running time은 θ(V + E)이다.

5-2. DFS의 특성

1) Predecessor subgraph G_π는 forest of trees를 형성한다.

2) u = v.π IFF(if and only if) u의 adjacency list를 검색하는 도중 DFS-VISIT(G, v)가 call되었을 경우

3) Vertex u는 vertex v의 descendant IFF u가 회색일 도중 v가 발견되었을 경우

4) 발견시간(v.d)과 종료시간(v.f)은 parenthesis structure를 가진다. 아래 b는 a의 parenthesization이다.

Parenthesis Theorem (Theorem 5-1)

어떤 undirected 혹은 directed graph G = (V, E)에 대한 모든 DFS에서, 모든 두 vertices u와 v는 아래 세 condition중 정확히 하나를 충족한다.

a) 구간 [u.d, u.f]와 [v.d, v.f]는 완전히 disjoint며, u나 v는 DFF(depth-first forest)에서 서로의 descendant가 아니다.

b) 구간 [u.d, u.f]는 [v.d, v.f] 내에 완전히 포함되어 있으며, u는 DFF에서 v의 descendant이다.

c) 구간 [v.d, v.f]는 [u.d, u.f] 내에 완전히 포함되어 있으며, v는 DFF에서 u의 descendant이다.

증명: u.d < v.d라고 하자. 

경우1) v.d < u.f일 경우, u가 회색일 때 v가 발견되었으므로 v는 u의 descendant다.

또한, v가 u보다 최근에 발견되었으므로, DFS가 u로 돌아가 종료하기 전에 v의 모든 outgoing edges를 검색 후 v를 먼저 종료할 것이다.

따라서 이 경우, [v.d, v.f]는 완전히 구간 [u.d, u.f]내에 속한다.

경우2) u.f < v.d일 경우, u.d < u.f에 의해  u.d < u.f < v.d < v.f 이다. 따라서 [u.d, u.f], [v.d, v.f] 두 구간은 disjoint다.

v.d < u.d일 경우에는 서로 치환해서 위와 같게 풀면 된다.

Corollary 5-1: 그래프 G(undirected or directed)의 DFF 내에서 vertex v는 vertex u의 proper descendant IFF u.d < v.d < v.f < u.f

증명: parenthesis theorem 참조

White-Path Theorem (Theorem 5-2): 그래프(undirected or directed) G = (V, E)의 DFF에서, vertex v는 vertex u의 descendant IFF u를 발견한 시간 u.d 때 u에서 v까지 white vertices로만 이뤄진 path가 있을 경우

→증명: 만약 v = u이면, u에서 v의 path는 그저 vertex u이고, u.d 때 white다.

이제 v가 DFF에서 u의 proper descendant라고 가정하면, 위의 corollary에 의해 u.d < v.d이고, 따라서 v는 u.d 시에 희다.

v가 u의 아무 descendant가 될 수 있으므로, DFF에서 u.d시의 u에서 v로의 unique simple path의 모든 vertices는 희다.

←증명: u.d 시에 u에서 v까지의 흰 vertices의 path가 있지만, v는 DFF에서 u의 descendant가 안된다고 하자.

그리고 그 path를 따라 v를 제외한 모든 vertices들이 u의 descendant가 된다고 하자. (without loss of generality)

(다르게 말하면, path에서 u의 descendant가 되지 않는 가장 가까운 vertex가 v라 하자)

만약 w가 path에 있는 v의 predecessor면, w는 u의 descendant이고(u=w일수도 있다) 위의 corollary에 따라 w.f ≤ u.f 이다.

v는 u의 발견보다는 늦게, w의 종료보다는 일찍 발견되어야 하므로, u.d < v.d < w.f ≤ u.f 이다.

그러면 Parenthesis Theorem에 의해 [v.d, v.f]는 구간 [u.d, u.f] 안에 완전히 포함된다. 위의 Corollary에 따라 v는 u의 descendant일 수밖에 없다.

5-3. Edge의 종류

1) Tree edge: DFF G_π의 edge들이다. 만약 v가 exploring edge (u, v)에 의해 처음 발견되면 edge (u, v)는 tree edge다.

2) Back edge: DFT(depth-first tree)에서 vertex u를 ancestor v로 연결하는 edge들이다. Directed graph에서 가능한 self-loop는 back edge로 분류한다.

3) Forward edge: DFT에서 vertex u를 descendant v로 연결하는 nontree edges를 말한다.

4) Cross edge: 모든 다른 edge들이다. 같은 DFT의 vertices 사이에도 한 vertex가 다른 vertex의 ancestor가 아닌 한 가능하고, 다른 DFT 사이에서도 가능하다.

앞서 그림 c는 a의 그래프를 새로 그려서 모든 forward edge가 아래를 향하고 back edge가 위로 가도록 그린 것이다.

DFS는 몇몇 edge는 encounter하자마자 분류가능하다.

만약 edge (u, v)를 처음 검색할 때, vertex v가 흰색이면 tree edge, 회색이면 back edge, 검정이면 forward 혹은 cross edge다.

Undirected 그래프의 경우, (u, v)와 (v, u)가 같으므로 모호할 수 있는데, 이럴 경우 둘 중 먼저 encounter하는 것으로 정한다.

그리고 forward와 cross edge는 undirected graph의 DFS에서 생기지 않는다.

Theorem 5-3: Undirected 그래프 G의 DFS에서 G의 모든 edge들은 tree edge 혹은 back edge이다.

증명: (u, v)가 G의 어떤 edge라 하고 u.d < v.d라 하자. 그러면 v는 u의 adjacency list에 있으므로 u 종료 전에 v를 발견하고 종료해야 한다.

처음으로 edge (u, v)를 발견했을 때, u에서 v로의 방향에 있으면 그때까지 v는 발견되지 않은 하얀 상태이다. (아니라면 DFS는 v에서 u로의 검색을 이미 행하였을 것이다)

따라서 (u, v)는 tree edge다. 만약 검색이 (u, v)를 v에서 u로의 방향에서 발견하면, 최초로 explore될 때 u가 아직 gray이므로, (u, v)는 back edge다.

5-4. Stack

4-4에서의 queue와 달리 stack은 LIFO 방식을 갖는 dynamic set다.

Stack의 INSERT operation은 PUSH라 불리고, DELETE operation은 POP이라 불린다.

n element를 가진 Array S가 있다하면 가장 최근에 삽입된 element를 index하는 S.top attribute가 있다.

Stack은 S[1, ..., S.top]으로 구성되고, S[1]은 가장 바닥에, S[S.top]은 가장 위의 element다.

따라서 S.top = 0일 때 stack은 empty다. STACK-EMPTY라는 query operation을 통해 확인 가능하다.

만약 empty stack을 pop하려하면 stack underflow를, S.top이 n을 초과하면 stack overflow를 초래한다.

아래는 PUSH와 POP의 operation을 보여주고, 각 O(1)이 걸린다.

(a)에서 stack은 4개 element를 가지고, (b)는 PUSH(S, 17), PUSH(S, 3)을 행한 후 모습이다. 

(c)에서 POP(S)는 element 3을 return한다. Element 3은 array에서는 아직 보이지만, stack에는 더 이상 존재하지 않는다.