[알고리즘-6]DFS의 응용

2016.09.29 12:51

최한철 조회 수:450

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

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

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


6-1. Topological Sort


"dag"는 directed acyclic graph를 말한다.

Dag G = (V, E)의 Topological sort는 어떤 edge (u, v)가 있으면 u가 v보다 먼저 오게 모든 vertices를 정렬하는 것이다.

즉, 모든 directed edge들이 왼쪽에서 오른쪽을 향하도록 하는 것이다.


TOPOLOGICAL-SORT(G)

1  DFS(G)를 call하여 각 vertex v에 대한 v.f를 계산한다.

2  각 vertex가 종료될 때마다 linked list의 처음으로 보낸다.

3  Linked list를 return한다.


아래의 b에서 topologically sorted vertices는 종료시간의 반대순으로 정렬된다는 것을 알 수 있다.

1.jpg


우리는 topological sort를 θ(V+E)에 행할 수 있는데, DFS가 θ(V+E) 시간 걸리고,

|V|개의 vertices들을 각각 linked list의 처음으로 보내는데 O(1)이 걸리기 때문이다.


이 알고리즘의 correctness 증명은, dag에 대한 아래의 lemma를 통해 한다.


Lemma 6-1: Directed 그래프 G는 acyclic IFF G의 DFS가 back edge를 형성하지 않을 때

→증명: DFS가 back edge를 형성한다면, 그러면 vertex v는 DFF에서 vertex u의 ancestor이다.

따라서 G는 v에서 u까지의 path를 포함하고, back edge (u, v)가 cycle을 완성한다.

←증명: G가 cycle c를 포함한다고 하면 G에 대한 DFS가 back edge를 형성함을 보인다.

v가 c에서 발견되는 첫 vertex라 하고, (u, v)가 c의 preceding edge라고 하자. 

v.d 시간에서 c의 vertices는 v에서 u까지의 white vertices의 path를 형성한다.

White-path theorem에 의해, vertex u는 DFF에서 v의 descendant가 된다.

따라서 (u, v)는 back edge다.


Theorem 6-1: 알고리즘 TOPOLOGICAL-SORT(G)는 input으로 제공된 dag의 topological sort를 제공한다.

증명: 주어진 dag G = (V, E)에서 DFS가 실행되서 각 vertices의 종료시간을 계산한다 하자.

그렇다면 어떤 두 distinct vertices u, v ∈ V의 pair에 대해, 만약 G가 u에서 v의 edge를 포함하면 v.f < u.f임을 보이면 충분하다.

그럼 이제 DFS(G)에 의해 explore된 edge (u, v)를 보자.

이 edge가 explore되었을 때, v는 회색일 수 없다. 왜냐면 회색이면 v는 u의 ancestor고 (u, v)는 back edge이라 Lemma 6-1에 반한다.

따라서 v는 희거나 검어야 한다. 만약 v가 흰색이면, u의 descendant고, v.f < u.f이다.

만약 v가 검정이면, 이미 종료되었으므로 v.f는 이미 결정되었다. 우린 아직 u를 검색중이므로 v.f < u.f이다.

따라서, dag의 그 어떤 edge (u, v)에 대해서도 v.f < u.f이므로 증명된다.


6-2. Strongly Connected Components


이제 2번의 DFS를 이용해 directed graph를 strongly connected components대로 decompose하는 방법을 보자.

Directed graph G = (V, E)의 SCC(strongly connected component)는 maximal set of vertices C ⊆ V로,

C 안의 각 pair of vertices u, v에 대해 각각 u ~> v가 있고 v ~> u가 있는 경우, 즉 u와 v가 서로 reachable한 경우이다.

2.jpg


그래프 G = (V, E)의 SCC를 찾는 알고리즘은 G의 transpose(각 edge가 reversed)를 사용한다. 

G의 adjacency-list representation가 주어졌다면, GT를 만드는 시간은 O(V + E)다.

G와 GT는 정확히 같은 SCC를 가진다. 그림 b는 a의 transpose이다.


아래의 linear time θ(V+E) 알고리즘은 각 G와 GT에 두 번의 DFS를 하여 SCC를 찾는다.


STRONGLY-CONNECTED-COMPONENTS(G)

1  DFS를 call하여 각 vertex u의 종료 시간 u.f를 계산한다.

2  GT를 계산한다.

3  DFS(GT)를 call하는데, DFS의 main loop에서 u.f가 decrease하는 순으로 vertices를 처리한다.

4  Line 3에서 형성된 DFF의 각 tree의 vertices를 제각각 SCC로 output한다.


이 알고리즘은 component graph GSCC = (VSCC, ESCC)의 특성을 이용하는데 이 component graph는 아래와 같이 정의된다.

G가 SCC C1, C2, ..., Ck가 있다하자. Vertex set VSCC는 {v1, ..., vk}이고, 각 SCC Ci에 대한 vertex vi를 포함한다.

어떤 x ∈ Ci, 어떤 y ∈ Cj 의 directed edge (x, y)가 G에 존재하면 edge(vi, vj) ∈ ESCC가 존재한다.

다시 말해, G에서 incident vertices가 똑같은 SCC내에 있는 edge들을 모두 contract하면 GSCC가 된다.

그림 c는 a의 component graph이다. 중요한 특성은 component graph은 dag란 것이다.


Lemma 6-2: Directed graph G = (V, E)에서 C와 C'가 distinct한 SCC고, u, v ∈ C이며 u', v' ∈ C'라 하자. 또한 G가 path u ~> u'를 포함한다 하자.

그러면 G는 path v' ~> v를 포함할 수 없다.

증명: 만약 G가 path v' ~> v를 가진다면, 그것은 u ~> u' ~> v'를 가지고 v' ~> v ~> u를 가진다. 

따라서 u와 v'는 서로에게 reachable하므로 C와 C'는 distinct SCC라는 가정과 상반된다.


우리는 첫번째 DFS에서 계산된 종료시간을 역순으로 두번째 DFS를 실행함으로써, component graph의 각 vertices를 topologically sorted order로 방문한다.

SCC는 두 번의 DFS를 사용하므로 u.d나 u.f가 헷갈릴 수 있는데, 여기서는 항상 첫번째 DFS를 말한다.


이제 우리는 발견시간과 종료시간의 개념을 vertices의 집합으로 확장한다.

U ⊆ V이면, d(U) = minu∈U{u.d}이고 f(U) = maxu∈U{u.f}으로 정의한다. 즉 d(U)와 f(U)는 U 내 vertex 중 가장 이른 발견시간과 가장 늦은 종료시간이다.


Lemma 6-3: C와 C'가 directed 그래프 G = (V, E)의 distinct SCC라 하자. 그러면 어떤 edge (u, v) ∈ E가 u ∈ C이고 v ∈ C'면, f(C) > f(C')이다.

증명: 두 경우를 본다. 

먼저, d(C) < d(C')일 경우, x가 C에서 최초발견된 vertex라 하자. x.d 시점에 C와 C'의 모든 vertex는 희다.

그리고 G는 x에서 C의 다른 모든 vertex로 향하는 white vertices path가 있다. 

(u, v) ∈ E이므로, 그 어떤 vertex w ∈ C'에 대해 x.d시점에 x에서 w로의 white vertices path 또한 있다. x ~> u → v ~> w

따라서 white-path theorem에 의해 C와 C'의 모든 vertices는 x의 descendants가 된다. 따라서 x는 가장 늦은 종료 시간을 가지고 그러므로 x.f = f(C) > f(C')이다.

반대로, d(C) > d(C')일 경우, y가 C'에서 최초 발견된 vertex라 하자.

시점 y.d에 C'의 모든 vertices는 희고 G에는 y에서 C'의 다른 모든 vertex로의 white vertices path가 있다.

White-path theorem에 의해, C'의 모든 vertices는 y의 descendants가 되고, y.f = f(C')이다.

시점 y.d에 C의 모든 vertices는 희다. C에서 C'로의 edge (u, v)가 있으므로, Lemma 6-2에 의해 C'에서 C로의 path가 있을 수 없다.

따라서 y에서 reachable한 C의 vertex는 존재하지 않는다. 그러므로 시점 y.f에 C의 모든 vertices는 희다. 

결론적으로 그 어떤 vertex w ∈ C에 대해, w.f > y.f이고 이는 f(C) > f(C')를 의미한다.


Corollary 6-1: C와 C'가 directed 그래프 G = (V, E)의 distinct SCC라 하자. 그러면 어떤 edge (u, v) ∈ ET가 u ∈ C이고 v ∈ C'면, f(C) < f(C')이다.

증명: (u, v) ∈ ET이므로 (v, u) ∈ E다. G와 GT의 SCC는 동일하므로, Lemma 6-3에 의해 f(C) > f(C')다.


Theorem 6-2: 프로시져 STRONGLY-CONNECTED-COMPONENTS는 directed 그래프 G를 input으로 받아 정확히 SCC를 계산한다.


댓글 0

목록
번호 제목 글쓴이 날짜 조회 수
공지 [공지]데이터 과학 게시판의 운영에 관하여 최한철 2016.04.23 95
22 [일반]데이터 사이언스 공부 사이트 정리 최한철 2018.09.23 98
21 [계량경제학]Nonparametric Smoothing file 최한철 2018.07.13 29
20 [계산통계학]Convex Functions 최한철 2017.02.14 233
19 [머신러닝]Support Vector Machine 최한철 2017.02.13 205
18 [계산통계학]Automatic Differentiation 최한철 2017.01.23 127
17 [시계열분석-8]시계열 모델과 예측 file 최한철 2016.12.04 199
16 [시계열분석-7]자기상관과 AR모델 file 최한철 2016.12.04 988
15 [시계열분석-6]추세의 모델링 file 최한철 2016.12.04 141
14 [회귀분석-5]회귀분석 결과의 해석 file 최한철 2016.12.03 135
13 [회귀분석-4]변수 선택 및 모델의 진단 file 최한철 2016.12.03 733
12 [회귀분석-3]다중 회귀 분석 II file 최한철 2016.10.12 81
11 [회귀분석-2]다중 회귀 분석 file 최한철 2016.10.09 630
10 [알고리즘-7]그래프의 최단 거리 최한철 2016.10.09 95
» [알고리즘-6]DFS의 응용 file 최한철 2016.09.29 450
8 [회귀분석-1]기본 회귀 분석 file 최한철 2016.09.25 326
7 [알고리즘-5]BFS의 응용 file 최한철 2016.09.19 475
6 [알고리즘-4]그래프 file 최한철 2016.09.18 910
5 [알고리즘-3]Master Theorem file 최한철 2016.09.15 321
4 [알고리즘-2]알고리즘 디자인 file 최한철 2016.09.10 379
3 [알고리즘-1]알고리즘의 정의 최한철 2016.09.08 238