Undirected Graph에서는 Connected Component를 구하려면 아무 Vertex나 잡고 DFS를 수행한 결과 생성되는 DFS Tree 가 Connected Component 였다.
(Definition of Connected Component of Graph G : G의 maximal 한 connected subgraph)
Directed Graph에서는 Connected를 Strongly Connected로 정의하는 것이 일반적이다.
그럼 Strongly Connected란 무엇일까?
Definition of Strongly Connected in Directed Graph
Directed Graph G에서 G에 속한 서로 다른 두 vertex v, u에 대하여 path v to u 와 path u to v가 모두 존재하면 두 vertex v, u는 strongly connected하다.
Strongly Connected Component (이하 SCC) 는 다음과 같이 정의한다.
Definition of Strongly Connected Component in Directed Graph
SCC G' of Graph G : G의 maximal strongly connected Subgraph
SCC의 특이한 property는 SCC는 Graph의 Vertex를 Disjoint하게 Partitioning 한다는 것이다.
이제 Graph에서 SCC를 어떻게 찾을지 생각해보자.
- G의 vertex v에 대해 DFS를 수행하고 Gr의 vertex v에 대해 DFS를 수행한 뒤 v에서 reachable한 vertex들의 set을 각각 S1, S2라하자. 이 때 S1과 S2의 교집합의 vertex set은 SCC를 이룬다.
*Gr = Directed Graph G의 모든 Edge들의 방향을 거꾸로 뒤집은 Graph.
1번 알고리즘의 정당성 증명
Statement : S = S1 ⋂ S2 에 속한 vertex 는 G의 strongly connected component 를 이룬다.proof : Contradiction. Graph G에 속한 vertex 중 S에 속하지 않으면서 SCC를 이루는 vertex u가 있다고 하자. 그러면 Strongly Connected의 정의에 의해 vertex u와 SCC의 임의의 vertex w간에 path u to w, path w to u 가 존재하게 된다. 그러면 Graph G의 u에서 reachable 한 vertex set S1과 Graph Gr의 u에서 reachable 한 vertex set S2 사이에는 w가 존재한다. 이는 vertex v가 S에 속하지 않는다는 조건에 위배되므로 모순이다.
1번 알고리즘은 정당하나, Gr을 구하는데에 O(n+m) + O(n*(n+m)) (n개의 vertex에서 reachable한 vertex set 구하기) = O(n(n+m))의 Time Complexity가 소요됨.
이 알고리즘은 정상 작동하나, 느리므로 다른 알고리즘을 생각해보자.
- DAG을 이용하기.
DAG이란?
Definition of DAG : Directed Acyclic Graph
DAG의 경우 DAG 상의 Vertex들 간의 Toplogical order를 정의할 수 있다.
Toplogical Order in DAG
Definition of Toplogocial Order in DAG : If there exists edge(u,v)[edge u to v] u means u is precedes v.
먼저 DAG상의 Source와 Sink의 정의에 대해 알아보자.
Definition of Source and Sink in DAG
Source : Vertex whose indegree is Zero.
Sink : Vertex whose outdegree is Zero.
DFS를 이용해서 DAG의 Toplogical Sort를 수행할 수 있다.
어떻게 ?
DAG에서 DFS를 수행한 결과 post(v)를 Decreasing Order로 정렬하면 그것이 Topological Order. 그러면, Post(v)가 가장 큰 vertex가 DAG의 Source가 되고, Post(v)가 가장 작은 vertex가 DAG의 Sink가 된다.
이 Property를 이용하여 SCC를 찾아보자.
먼저 Graph G에서 SCC를 Vertex로 취급하여 SCC S1에서 SCC S2로 가는 Edge(s1,s2)가 존재할 때 그 edge를 추가한 그래프를 Gd라고 하자.
그럼 Gd는 DAG이 된다. Why?
Proof
Gd가 DAG이 아니라면 (Cycle이 존재한다면) S1과 S2가 SCC이기 위한 조건인 Maximality가 훼손된다.
Gd가 DAG인 상태에서 Topological Order를 수행해준 뒤, Sink가 되는 Vertex(=One SCC in Graph G)에 속하는 아무 Vertex(=One vertex in Graph G에 대해서 DFS를 수행해주면 그 Sink Vertex에 대해 reachable한 모든 vertex를 찾을 수 있다.
Q1. 그렇다면 우리는 Sink Vertex에 속한 어떤 vertex 하나를 찾을 수 있어야 한다. 어떻게 찾을 수 있을까?
이것의 해결을 위해 다음 성질을 이용하자.
** Property : Gd에 Edge(S1, S2) (S1, S2 : 서로 다른 SCC in Graph G)가 존재할 때, Graph G에 대해 DFS를 수행한 결과 S1에 속한 모든 Vertex의 Post(v)는 S2에 속한 모든 Vertex의 Post(v)보다 크다.
Proof
Case 1. S1에 속한 vertex에서 DFS
S2에 속한 모든 Vertex는 S1에 속한 어떤 Vertex에 대해서도 Reachable 하다. 즉 S2에 속한 Vertex는 DFS Tree에서 S1에 속한 어떤 Vertex에 대해서도 Descendant로 나타난다.Case 2. S2에 속한 Vertex에서 DFS
DFS Tree에서 S2에 속한 어떠한 Vertex에 대해서도 S1에 속한 Vertex를 Descendant로 가질 수 없다. 즉, S2에 속한 모든 Vertex를 explore한 다음에 S1을 Explore하게 된다. <S2와 S1은 서로 다른 Tree에 존재하게 됨!>
즉, 우리는 G에서 DFS를 하면 Post(v)가 가장 큰 vertex를 찾을 수 있고 이 Vertex는 Gd의 Source에 속한 Vertex가 된다.
Grd를 Gd에서 Edge의 방향을 모두 뒤집은 그래프로 정의하자.
그러면 Gd의 Source는 Grd의 Sink가 되고, Gd의 Sink는 Grd의 Source가 된다.
Grd에서 DFS를 수행하고, Post(V)가 가장 큰 vertex(One Vertex in Graph G)를 골랐을 때 이 Vertex는 Gd의 Sink에 속한 vertex가 된다! --> Q1. 해결!!
방금 찾은 vertex에 대해서 DFS를 수행해주면 이 Vertex에서 Reachable한 Vertex set은 Gd의 Sink가 되고 (G \ 방금 찾은 Vertex set)에 대해서 이 방법을 재귀적으로 수행해주면 Graph G의 모든 SCC Component를 찾아낼 수 있다.
Pseudo Code
DFS(Gr) and Sort Vertices in decreasing order (post(v))
Initialize all vertex are not visited.
For each vertex v in sorted Order:
if v is not visited:
DFS(v) on Graph G
Let Sv = vertices set reachable from vertex v
Print Sv as a SCC.
Remvoe Sv from G(V)[G의 Vertex set]
