『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는 종료시간의 반대순으로 정렬된다는 것을 알 수 있다.

우리는 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한 경우이다.

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

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

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

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

STRONGLY-CONNECTED-COMPONENTS(G)

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

2  G^T를 계산한다.

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

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

이 알고리즘은 component graph G^SCC = (V^SCC, E^SCC)의 특성을 이용하는데 이 component graph는 아래와 같이 정의된다.

G가 SCC C₁, C₂, ..., C_k가 있다하자. Vertex set V^SCC는 {v₁, ..., v_k}이고, 각 SCC C_i에 대한 vertex v_i를 포함한다.

어떤 x ∈ C_i, 어떤 y ∈ C_j 의 directed edge (x, y)가 G에 존재하면 edge(v_i, v_j) ∈ E^SCC가 존재한다.

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

그림 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) = min_u∈U{u.d}이고 f(U) = max_u∈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) ∈ E^T가 u ∈ C이고 v ∈ C'면, f(C) < f(C')이다.

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

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