[알고리즘] 그래프 (7) - 강한 연결 요소 (Strongly Connected Components)

 

 

 

 

🧐 Strongly Connected

방향 그래프에서는 무방향 그래프와 동일하게 Connectivity(연결성)를 정의할 수 없습니다.

 

방향 그래프에서의 Connectivity는 보통 Strongly Connected 로 정의되며, 해당 정의는 다음과 같습니다.

$G$ 는 Strongly Connected 하다 :

임의의 서로 다른 두 정점 $v$, $u$ $\in V(G)$ 에 대하여,

$v$ 에서 $w$ 로의 Path와,
$w$ 에서 $v$ 로의 Path가 존재한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Strongly Connected Components (강한 연결 요소)

그래프 $G$에 대한 Strong Connected Component $G'$ :

$G$ 의 Maximal Strongly Connected Subgraph

 

$G$ 의 Strongly Connnected Component는 $G$ 의 Vertex 들을 Partitioning 합니다.

 

 

 

 

이제부터 어떠한 방향 그래프 $G$ 가 주어졌을 때, $G$ 의 강한 연결 요소(SCC)를 찾는 알고리즘을 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 SCC 알고리즘 - 1

가장 간단한 방법은 다음과 같습니다.

 

 

방향 그래프 $G$ 의 모든 edge들의 방향을 뒤집은 그래프를 $G^R$ 이라고 하겠습니다.

 

 

$G$ 와 $G'$ 을 사용하여 SCC를 찾아냅니다.

그래프에 존재하는 각각의 정점 $v$ 에 대하여, $G$ 와 $G^R$ 로부터 explore를 수행합니다.

$G$ 에서 reachable한 정점들의 집합을 $S_1$ 이라 하고,
$G^R$ 에서 reachable한 정점들의 집합을 $S_2$ 라 하겠습니다.

이때 $S = S_1 \cap S_2 $ 에 속한 정점들은, $G$ 의 SCC를 이룹니다.

 

 

👉 증명

 

주장

$S = S_1 \cap S_2 $ 에 속한 정점들은, $G$ 의 SCC를 이룬다.

 

증명

$S$ 에 속한 임의의 두 정점을 $u$, $w$ 라 하겠습니다.

$S$ 의 정의에 의하여,

(1) $v$ 에서 $u$ 로의 Path, ($G$ 에 의하여)
(2) $u$ 에서 $v$ 로의 Path, ($G^R$ 에 의하여)
(3) $v$ 에서 $w$ 로의 Path, ($G$ 에 의하여)
(4) $w$ 에서 $v$ 로의 Path, ($G^R$ 에 의하여)

가 존재합니다.

(2)와 (3)을 통해 $u$ 에서 $w$ 로의 Path가 존재하며

(4)와 (1)을 통해 $w$ 에서 $u$ 로의 Path가 존재합니다.

따라서 $S$ 에 속한 정점들은 $G$ 의  SCC를 이룹니다.

 

 

이때 maximality 에 대한 증명은 다음과 같습니다.

$S_1 \cap S_2$ 에 속하는 정점들과 간선으로 구성된 그래프 $G'$ 에 대하여,
해당 그래프 $G'$ 가 Strongly Connected 하지만 maximal 조건은 충족하지 않는다고 가정하겠습니다.

그렇다면 $G'$ 에 속하지 않으며 기존 그래프 $G$ 에는 존재하는 임의의 정점 $u$ 에 대하여,
이들로 이루어진 $G'$ 보다 더 큰 Strongly Connected Graph가 존재합니다. 이를 $G_m$ 이라 정의하겠습니다.

일반성을 잃지 않고 해당 정점 u가 S_1에 존재한다고 하겠습니다.
$S_1 \cap S_2$ 에 속하는 임의의 정점 $v$ 에 대하여, $v$ 와 $u$ 는 $G_m$ 에 속하므로
$v \to u$ 로의 path와 $u \to v$ 로의 path가 존재해야 합니다.

그러나 $u$ 는 $S_1$ 에는 속하지만 $S_1 \Cap S_2$ 에 속하지 않으므로 $u \to v$ 로의 path가 존재하지 않습니다.

따라서 가정에 모순이 발생하였고, 증명이 완료됩니다.

 

 

 

 

 

 

시간 복잡도

$n$ : 정점의 개수
$m$ : 간선의 개수

$G^R$ 을 구하는 데 드는 시간 : $O(n + m)$

모든 정점들에 대하여 $G$ 와 $G^R$ 에서 explore를 수행하는 시간 : $n \times O(n + m)$

따라서 $O(n(n+m))$ 안에 $G$ 의 모든 SCC를 구할 수 있습니다.

 

그러나 이는 너무 느리며, 좀 더 빠른 알고리즘을 살펴보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 SCC 알고리즘 - 2

 

두번째 알고리즘은 DAG를 이용한 방법입니다.

 

 

두번째 알고리즘의 설명을 위해 $G_d$ 를 정의하도록 하겠습니다.

방향 그래프 $G$ 에 대하여,

$G$ 의 각 SCC 를 하나의 정점($S_1, S_2, ...$)으로 두고,

$S_1$ 에서 $S_2$ 로 가는 Edge(간선)가 존재하면,

Edge($S_1$ ,$S_2$) 를 추가한 방향 그래프를 $G_d$ 라 하겠습니다.

 

 

 

이때 $G_d$ 는 DAG 입니다.

 

만약 DAG가 아닌 경우, maximal 조건을 위배하게 됩니다.

 

 

👉 증명

 

어떤 그래프 $G$ 에 대하여, $G$ 에 속하는 strongly connected component $V_1, V_2, ... V_n$ 으로 이루어진 $G_d$ 에 대하여, $G_d$ 에 Cycle이 존재한다고 가정하겠습니다.

$G_d$ 에는 Cycle이 존재하며, 해당 Cycle에 존재하는 두 정점을 $V_n, V_m$ 이라 하겠습니다.

이때 $V_n$ 에 속한 임의의 정점 $w$ 와, $V_m$ 에 속하는 임의의 정점 $u$ 에 대하여 $u \to w$ 로의 path와 $w \to u$ 로의 path가 존재합니다.

$V_n + \left\{ u \right\}$ 는 Strongly Connected이며 $V_n$ 보다 크기가 크기 때문에 $V_n$ 은 Maximal 조건을 만족하지 않으므로 SCC라는 가정에 모순입니다.

 

 

 

 

 

 

이제 DAG를 이용하여 그래프 $G$ 의 SCC를 찾아내는 과정을 살펴보도록 하겠습니다.

 

 

먼저 $G_d$ 는 다음과 같은 속성을 가집니다.

$G_d$ 의 sink(OutDegree = 0) $s$ 에 속한 아무 정점 $v$ 로부터 reachable한 node들의 집합은,

$G$ 에서 하나의 SCC 집합을 이룹니다.

즉 $G_d$ 의 sink에 속한 아무 정점으로부터 explore를 진행하면 SCC 하나를 반환받을 수 있습니다.

 

 

 

 

$G_d$ 를 사용하여 $G$ 의 SCC 하나를 얻어내는 방법은 알아냈으나, 다음과 같은 두가지 문제가 새로 생겼습니다.

 

1. $G_d$ 의 sink에 속한 정점들 중 하나를 어떻게 찾을 수 있나?
2. $G_d$ 의 sink에 해당하는 SCC를 찾은 후, 나머지 SCC들은 어떻게 찾을 수 있을까?

 

 

 

이제 해당 문제들을 해결하는 방법을 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

첫번째 문제 : $G_d$ 의 Sink에 속한 정점 찾아내기

 

$G_d$ 의 Sink에 속한 정점을 찾아내는 것은 어렵지만,

 

$G_d$ 의 Source에 속한 정점들은 다음 속성에 의해 쉽게 찾을 수 있습니다.

 

$G_d$ 의 두 정점(즉 $G$ 에서의 SCC) $S_1$, $S_2$ 에 대하여, 

Edge($S_1$, $S_2$) 가 있다고 가정하겠습니다.

$G$ 에서 DFS를 하면,

$S_1$ 의 가장 큰 post number($S_1$ 의 모든 정점들 중 postOrder 값이 가장 큰 정점) 는 언제나
$S_2$ 의 가장 큰 post number 보다 큽니다.

 

👉 증명

 

Case 1

$S_1$ 에 존재하는 정점 $v$ 로부터 explore를 수행하는 경우,

Edge($S_1$, $S_2$)  가 존재하므로, 

$S_2$ 의 모든 정점은 $v$ 에서 Reachable합니다.

즉 DFS Tree에서 $S_1$, $S_2$ 의 모든 정점들이 $v$ 의 Descendent입니다.

따라서 $S_1$ 의 post number가 $S_2$ 의 post number보다 큽니다.

 

Case 2

$S_2$ 에 있는 정점 $u$ 로부터 explore를 수행하는 경우,

$u$ 를 root로 가지는 DFS Tree 는 $S_1$ 의 어떠한 정점들도 Descendent로 가질 수 없습니다.

따라서 $S_2$ 에 있는 정점들을 explore 한 뒤 $S_1$ 에 있는 정점들을 explore 하게 됩니다.

따라서 $S_1$ 의 post number가 $S_2$ 의 post number보다 큽니다.

 

 

 

 

 

 

 

위 속성을 통해 $G_d$ 의 Sink에 속한 정점을 쉽게 찾아낼 수 있습니다.

위 속성에 의해 $G_d$ 의 Source(InDegree = 0)는 $G$ 에서 가장 큰 post number를 가진 정점을 무조건 포함합니다.

$G_d$ 와 $G^{R}_{d}$ 는 같은 Vertex Set을 가지고 있으므로( 즉 같은 SCC를 가지고 있으므로 ),
$G_d$ 의 Sink는 $G^{R}_{d}$ 의 Source 입니다.

따라서 $G^R$ 에서 DFS를 수행한 후, 가장 높은 PostOrder 값을 가진 정점(즉 $G^{R}_{d} $ 의 Source 에 속한 정점)은 
$G_d$ 의 Sink에 무조건 속해 있습니다.

(첫번째 문제 해결!)

 

 

 

 

 

 

 

 

 

 

두번째 문제 : $G_d$ 의 Sink에 해당하는 SCC를 찾은 후, 나머지 SCC 찾아내기

$G^{R}_{d}$ 에서 Source를 제거한 뒤,

$G^{R}_{d}$ 의 Source에 해당하는 정점들을 $G$ 에서 제거하더라도,

위에서 살펴본 속성에 의하여, 남아있는 정점들 중에서 가장 Post Number가 큰 정점은 

새로운( = Source가 제거된) $G^{R}_{d}$ 의 Source, 즉 $G_d$ 의 Sink에 속합니다.

따라서 남아있는 정점들에 대하여 위 과정을 재귀적으로 수행하여 구할 수 있습니다.

 

 

 

 

 

 

 

 

수도코드

 

 

 

 

 

 

 

예시

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

⭐️ 연습문제

다음은 백준에 있는 SCC 기본 문제입니당

한번 풀어보세용 :D

 

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component