[Algorithms] Strongly Connected Components | 강연결 요소

Strongly Connected Components

강연결 요소

- Directed Graph \(G = (V, E)\)에서 모든 \((u ,v) \in E\)에 대해,
  경로 \(u \rightsquigarrow v\) 와 경로 \(v \rightsquigarrow u\) 가 동시에 존재하면,
  그래프 \(G\)는 "Strongly Connected"("강하게 연결되어 있다")라 표현한다.
- 즉, 어떤 두 정점을 잡더라도 양방향으로 서로에게 이르는 경로가 존재하면 "강하게 연결되어 있다"라 표현할 수 있다.
- 그래프상에서 강하게 연결된 부분 그래프들을 각각 Strongly Connected Components(강연결 요소)라 부른다.

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

---

Mechanism (원리)

Phase	Description
(a)	- 주어진 그래프 \(G\)이다.
(b)	- 정점 내부에 1로 표기된 정점을 시작으로 하여, \(\texttt{aDFS()}\)를 수행한 결과이다.   (정점 내부의 숫자는 방문한 순서를 의미하며, 시작점은 임의로 선정한다.) - \(\texttt{aDFS()}\) 수행 결과, 10개 정점 중 8개의 정점이 방문되었음을 확인할 수 있다. - 정점 바깥의 숫자는 각 정점의 완료 시간, \(\texttt{f[v]}\)를 의미한다.   \(\texttt{f[v]}\)는 DFS를 수행하며 정점 \(v\)에 대해 더 이상 할 일이 없는 상태가 된 시점을 의미한다.
(c)	- 그래프상에서, 아직 방문하지 않은 정점들 중 하나를 임의로 선정하여   Phase (b)에서와 같이 \(\texttt{aDFS()}\)를 수행한다.
(d)	- 그래프 \(G\)를 Transpose하여 \(G^T\)를 구성한다. - 이 그림에서부터는 정점안에 표기된 값은 방문 순서가 아니고, 완료 시간 \(\texttt{f[v]}\)임에 유의하자.   (Phase (a), (b)에서 정점안의 값은 방문 순서이고, Phase (c)부터 정점안의 값은 \(\texttt{f[v]}\)이다.)
(e)	- \(G^T\)를 대상으로 \(\texttt{aDFS()}\)를 수행하되, \(\texttt{f[v]}\)가 가장 큰 정점을 시작 정점으로 한다. - \(\texttt{f[v]}\) = 10인 정점부터 시작하는데, 이 정점은 진출 간선이 없어 본인만 방문하고 \(\texttt{aDFS()}\)가 완료된다.   (즉, \(\texttt{f[v]}\) = 10인 정점 한 개를 원소로 하는 집합이 구성된다.)
(f)	- \(G^T\)에서 이전 단계인 Phase (e)에서 \(\texttt{aDFS()}\)를 수행한 정점들은 제외하고,   \(\texttt{f[v]}\)가 가장 높은 정점을 선정하여 \(\texttt{aDFS()}\)를 수행한다.   (그 결과, 이번에도 \(\texttt{f[v]}\) = 9인 하나의 정점이 방문되고, 이 1개의 정점을 원소로 하는 집합이 구성된다.)
(g)	- Phase (f)와 같이, 방문되지 않은 정점 중 \(\texttt{f[v]}\)가 가장 큰 정점을 선정하여 \(\texttt{aDFS()}\)를 수행한다. - 그 결과, 이번에는 \(\texttt{f[v]}\) = 8인 정점부터 시작하여 다섯 개의 정점이 방문되고,   이 5개의 정점을 원소로 하는 집합이 구성된다.
(h)	- 이전과 같이, 방문되지 않은 정점 중 \(\texttt{f[v]}\)가 가장 큰 정점을 선정하여 \(\texttt{aDFS()}\)를 수행한다. - 그 결과, 이번에는 \(\texttt{f[v]}\) = 3인 정점부터 시작하여 세 개의 정점이 방문되고,   이 3개의 정점을 원소로 하는 집합이 구성된다.
(i)	- \(G^T\)에서 방문되지 않은 정점은 없으므로, 강연결 요소 분리 알고리즘을 종료한다. - 알고리즘 수행 결과, 4개의 집합이 분리되었으므로,   그래프 \(G\)상에서 강연결 요소는 4개로 구성될 수 있음을 확인할 수 있다.

Example. 그래프 상에서 강연결 요소를 찾아내는 예시

- 그림에서 음영 영역으로 묶인 정점들은 같은 강연결 요소에 속하는 정점들이다.
  (즉, 각 음영 영역은 하나의 강연결 요소들이다.)
- 진한 회색 정점은 강연결 요소 트리의 루트 노드이다.
- 음영 처리된 간선은, 강연결 요소 트리의 간선이다.
- 각 정점들에 표시된 값은 (DFS 방문 순서/종료 시간)을 의미한다.
  (종료 시간 = \(\texttt{f[v]}\)이다.)
- (c)는 각 강연결 요소들을 하나의 정점으로 남겨 표현한 Acyclic Component Graph \(G^{SCC}\)이다.

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

strongly_connected_components(G)
// G = (V, E) : Given Graph
// G^T : Transposed Graph
{
    call DFS(G) to compute finishing times u.f for each vertex u;
    compute G^T
    call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing u.f;
    output the vertices of each tree in the depth-first forest formed in line 6 as a separate strongly connect component;
}

---

Performance (성능)

Time Complexity : \(\Theta(|V|+|E|)\)
\(V\) : Set of Vertices of Graph \(G\)
\(E\) : Set of Edges of Graph \(G\)

- \(\texttt{DFS()}\)를 수행하는데는 \(\Theta(|V|+|E|)\)의 시간이 소요된다.
- 그래프 \(G\)를 Transposed Graph \(G^T\)로 구성하는 작업은 모든 간선을 한 번씩 방문하며 방향을 바꾸는 작업이므로
  여기에는 \(\Theta(|V|+|E|)\)의 시간이 소요된다.

- 즉, 강연결 요소를 찾는 알고리즘의 수행 시간은 \(\Theta(|V|+|E|)\)이다.

---

Verification (검증)

Theorem. 강연결 요소를 찾아내는 알고리즘에서,
그래프 \(G\)를 Transpose한 \(G^R\)에 대해 \(\texttt{aDFS()}\)를 한 번 수행할 때 마다
리턴되는 Tree(Set of Vertices)에 속하는 정점들은
같은 강연결 요소에 속한다.

pf) 같은 트리(집합)에 속하는 두 정점 \(x, y\)가 있다 하자.
해당 트리의 루트 노드를 \(r\)이라 할 때, \(x, y\)가 이 트리에 속해있으므로,
\(G^R\)에서 경로 \(r \rightsquigarrow x\)와 경로 \(r \rightsquigarrow y\)가 존재한다. (그림 10-29(a))

그래프 \(G^R\)는 그래프 \(G\)에서 간선들의 방향만 반전시킨 그래프이므로,
\(G\)에는 경로 \(x \rightsquigarrow r\)과 경로 \(y \rightsquigarrow r\)이 존재한다. (그림 10-29(b))

그래프 \(G\)에 경로 \(r \rightsquigarrow x\)와 경로 \(r \rightsquigarrow y\)도 존재한다면,
경로 \(x \rightsquigarrow r \rightsquigarrow y\)와 경로 \(y \rightsquigarrow r \rightsquigarrow x\)가 존재하게 되어,
\(x, y\)는 서로에게 이르는 경로가 존재하게 되므로, 같은 강연결 요소에 속함이 증명된다. (그림 10-29(c))

이제, 그래프 \(G\)에 경로 \(r \rightsquigarrow x\)와 경로 \(r \rightsquigarrow y\)가 존재함을 귀류법을 통해 증명하자.
경로 \(r \rightsquigarrow x\)가 존재하지 않는다 가정하자.
\(\texttt{DFS(G)}\)를 수행할 때, \(r\)을 \(x\)보다 먼저 방문했다면, 경로 \(r \rightsquigarrow x\)가 존재하지 않는다 했으므로,
\(r\)의 완료 시간(\(\texttt{f[r]}\))이 \(x\)의 완료 시간(\(\texttt{f[x]}\))보다 빠르다(작다).

\(x\)를 \(r\)보다 먼저 방문했다면,
경로 \(x \rightsquigarrow r\)이 존재하므로, \(r\)에 이르게 되고,
\(r\)의 완료 시간이 \(x\)의 완료 시간보다 빠르게 된다.
즉, \(r \rightsquigarrow x\)가 존재하지 않으면, 어떤 경우든 경로 \(r\)의 완료 시간이 \(x\)의 완료 시간보다 빠르게 된다.
그런데, \(r\)은 \(\texttt{DFS}(G^R)\)에서 만들어진 트리의 루트이므로,
해당 트리에서 가장 완료시간이 오래 걸려야 하는 정점이므로 이는 모순이다.
그러므로, 경로 \(r \rightsquigarrow x\)는 반드시 존재해야 한다.
(이와 같은 논리로, 경로 \(r \rightsquigarrow y\)가 존재함을 증명할 수 있다.) (그림 10-29(c))

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)