이전 시간까지 Minimal Spanning Tree, 즉 MST를 구하는 기본적인 방법을 배워봤습니다.
이번엔 MST를 구하는 두 가지 방법 중 두 번째 프림 알고리즘을 배워볼겁니다. 

- Kruskal’s Algorithm 
- Prim’s Algorithm (오늘 배울거)

참고 : 가벼운 간선과 같은 용어를 모르신다면 MST를 공부하시면 됩니다.

https://kimyir.tistory.com/133

프림 알고리즘은 항상 하나의 트리를 구축합니다. 

즉, 알고리즘이 진행되는 동안 항상 연결된 트리 구조를 유지합니다.

프림 알고리즘의 시작은 임의의 정점(루트)에서 시작합니다. 이 정점은 MST의 시작점이 됩니다.

이걸 r이라고 하겠습니다.

각 단계에서 MST에 포함된 정점 집합 V𝐴 와 포함되지 않은 정점 집합 V − V𝐴 사이의 "가벼운 간선(light edge)"을 찾습니다.
가벼운 간선은 MST에 추가할 수 있는 최소 가중치의 간선입니다.

선택된 가벼운 간선을 MST에 추가하고, 해당 간선에 연결된 정점을 MST에 포함시킵니다.

정리하자면 

1. 현재 MST에 포함된 정점 집합 V𝐴 를 유지합니다.

2. V𝐴 와 V − V𝐴 사이의 가벼운 간선을 찾습니다.
3. 이 간선을 MST에 추가하고, 해당 간선에 연결된 정점을 V𝐴에 포함시킵니다.
4. 모든 정점이 MST에 포함될 때까지 이 과정을 반복합니다.

의사코드

프림 알고리즘에서는 우선순위 큐(Q)를 사용하여 가벼운 간선을 효율적으로 찾습니다.
큐의 각 객체는 MST에 포함되지 않은 정점  V − V𝐴 에 들어있습니다.

각 정점 v의 키 값은 MST에 포함된 정점 u와의 간선 중 최소 가중치를 나타냅니다. 

즉, u ∈ V𝐴 인 모든 간선 (u, v)의 최소 가중치입니다.
이 키 값은 해당 정점이 MST에 추가될 때의 가중치를 나타냅니다.

우선순위 큐에서 EXTRACT-MIN 연산을 수행하면, MST에 추가할 정점 v가 반환됩니다.
이 정점은 MST에 포함된 정점 V𝐴와 연결된 가벼운 간선을 가진 정점입니다.

만약 정점 v가 MST에 포함된 정점과 인접하지 않다면, 그 키 값은 무한대(∞)로 설정됩니다. 

이는 해당 정점이 현재 MST에 추가될 수 없음을 나타냅니다.

다시 정리하자면

알고리즘의 입력으로 주어진 루트 정점 r에서 시작합니다. 이 정점은 MST의 시작점이 됩니다.
r는 알고리즘에 입력으로 주어지지만, 임의의 정점이 될 수 있습니다.

각 정점은 트리에서 자신의 부모를 알고 있습니다. 이 정보는 π[v]라는 속성으로 저장됩니다.

π[v]는 정점 v의 부모를 나타내며, 루트 정점 r의 경우 π[v]=NIL로 설정됩니다. 

이는 루트 정점이 부모가 없음을 의미합니다.

해당 공식은 알고리즘 진행되면서 MST에 포함되지 않은 정점 집합 V−{r}−Q에 대해 각 정점과 그 부모 정보를 저장합니다.

알고리즘이 종료되면, V𝐴 = V가 되고 Q = ∅이 됩니다. 큐가 비게 됩니다. 즉, 모든 정점이 MST에 포함됩니다.

결국 MST는 이렇게 표현됩니다.

시간 복잡도

시간 복잡도는 우선순위 큐가 어떻게 구현되었는지에 따라 달라집니다. 이진 힙(binary heap)을 사용한다고 가정합시다.

우선순위 큐 Q를 초기화하고 첫 번째 for 루프를 수행하는 데 필요한 시간 복잡도는 O(V log V)입니다.
여기서  V는 정점의 수입니다.

루트 정점 r의 키 값을 감소시키는 데 필요한 시간 복잡도는 O(log V)입니다.

  
|V|번의 EXTRACT-MIN 호출이 필요하므로, 이 부분의 시간 복잡도는 O(V log V)입니다.

간선의 수 |E|에 비례하여 DECREASE-KEY 호출이 발생하므로, 이 부분의 시간 복잡도는 O(E log V)입니다.

결국 다 더하면 O(V log V)+O(E log V)가 되지만, 일반적으로 |E|가 |V|² O(E logV)가 더 지배적인 항이 됩니다.

이 내용은 전포스팅 크루스칼 알고리즘에서도 다뤘습니다. 따라서 O(V log V)는 생략해도 됩니다.

결론적으로 프림알고리즘의 시간복잡도는 O(E log V) 입니다.

크루스칼 알고리즘 vs 프림 알고리즘

크루스칼 알고리즘:

간선 중심의 접근 방식입니다. 

모든 간선을 가중치에 따라 정렬한 후, 가장 낮은 가중치의 간선부터 선택하여 MST에 추가합니다.
사이클을 형성하지 않도록 유니온-파인드 자료구조를 사용하여 간선을 선택합니다.

프림 알고리즘:

정점 중심의 접근 방식입니다. 

임의의 정점에서 시작하여 MST에 포함된 정점과 포함되지 않은 정점 사이의 가벼운 간선을 선택하여 MST를 확장합니다.
현재 MST에 연결된 정점과 연결되지 않은 정점 사이의 최소 가중치 간선을 선택합니다.

부록

만약 경로의 weight, 가중치가 마이너스라면 알고리즘이 작동할까요?

네 그래도 알고리즘이 작동됩니다.

이전 시간까지 Minimal Spanning Tree, 즉 MST를 구하는 기본적인 방법을 배워봤습니다.

이제부턴 Minimal Spanning Tree를 구하는 두 가지 방법 중 첫 번째 크루스칼 알고리즘을 배워볼겁니다. 

- Kruskal’s Algorithm (오늘 배울거)

- Prim’s Algorithm

정의

크루스칼 알고리즘은 결국 MST처럼 최소 비용의 경로를 찾는겁니다. 그전에 정의부터 설정하겠습니다.

그래프 G는 비방향 가중치 그래프입니다.

w : E→R

w는 가중치고 E는 그래프 G의 간선 집합입니다. R은 실수 집합입니다.

즉, w는 간선 집합 E의 각 간선에 대해 실수 값을 매핑하는 가중치 함수입니다. 

알고리즘은 각 정점이 자신의 컴포넌트로 시작합니다. 즉, 초기에는 모든 정점이 독립적으로 존재합니다.

알고리즘은 반복문을 돌려서 두 개의 컴포넌트를 선택하여 연결하는 Light edge를 선택하여 병합합니다. 

이 간선은 컷을 가로지르는 가장 작은 가중치의 간선입니다.

뜻이 뭔지 모르겠다면 저번 포스팅을 다시 보시면 됩니다.

https://kimyir.tistory.com/133

간선 집합을 가중치에 따라 오름차순으로 스캔합니다. 즉, 가장 작은 가중치의 간선부터 선택합니다.

알고리즘은 불일치 집합(Disjoint Set) 자료구조를 사용하여 간선이 서로 다른 컴포넌트를 연결하는지 확인합니다. 

이를 통해 사이클을 방지합니다.

그럼 이를 통해 의사코드를 보시겠습니다.

의사코드

코드를 분석해봅시다.

A를 초기화 : O(1) -> MST 집합 A를 초기화하는 데 상수 시간이 소요됩니다.

첫 for 반복문 : |V| MAKE-SETs -> 각 정점에 대해 MAKE-SET을 호출하므로 O(|V|)의 시간이 소요됩니다.

E를 정렬 : O(E logE)  -> 간선 집합 E를 가중치에 따라 정렬하는 데 걸리는 시간입니다.
두 번째 for 반복문 : O(E) FIND-SETs and UNIONs -> 각 간선에 대해 FIND-SET과 UNION을 호출하므로 O(E)의 시간이 소요됩니다.

Find - SET과 Unions에 대해서 아래에서 설명드리겠습니다.

불일치 집합 데이터 구조

disjoint-set data structure, 즉 불일치 집합 자료구조를 사용하여 효율적으로 FIND-SET과 UNION을 수행합니다.

불일치 집합 자료구조(Disjoint Set Data Structure), 또는 유니온-파인드(Union-Find) 자료구조는 서로 겹치지 않는 집합을 효율적으로 관리하기 위한 자료구조입니다. 

Find : 특정 원소가 속한 집합의 대표 원소(루트)를 찾는 연산입니다. 이 연산은 경로 압축(Path Compression)을 통해 최적화할 수 있습니다.
Union : 두 개의 집합을 하나로 합치는 연산입니다. 이 연산은 union by rank 또는 union by size 기법을 사용하여 트리의 높이를 최소화합니다.

예시 

1. 의사 코드에 있던 과정처럼 초기화를 먼저합니다.

각 Vertex 별로 하나의 Component를 생성합니다. Disjoint-set |V|개를 생성합니다.
초기화하면 {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i} 로 구성된 Set이 만들어집니다.

2. 간선의 가중치 오름차순으로 정렬합니다.

weight가 가장 작은 1부터 12까지 정렬합니다.

3. 간선 선택 후 Union 연산합니다.

가장 작은 가중치 1이었던 간선(c, f)를 먼저 선택합니다.

find(c)와 find(f)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(c, f)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, f}, {d}, {e}, {g}, {h}, {i}

그 다음으로 작은 가중치인 2 간선(g, i)를 선택합니다.

find(g)와 find(i)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(g, i)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, f}, {d}, {e}, {g, i}, {h}

그 다음으로 작은 가중치인 3 간선 (e, f)를 선택합니다.

find(e)와 find(f)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(e, f)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, e, f}, {d}, {g, i}, {h}

이런 식으로 계속 진행하여 모든 정점이 연결될 때까지 반복합니다. 

각 단계에서 사이클이 형성되지 않도록 주의하며, 최종적으로 최소 신장 트리를 구성하게 됩니다.

크루스칼 알고리즘으로 결과적으로 생성된 MST 결과입니다.

시간 복잡도

크루스칼 알고리즘의 첫 번째 단계는 모든 간선을 가중치에 따라 정렬하는 것입니다.
이 단계의 시간 복잡도는 O(E log E)입니다. 

여기서 E는 간선의 수입니다. 정렬 알고리즘의 일반적인 시간 복잡도가 로그 시간 복잡도를 포함하기 때문입니다.

두 번째 단계는 각 간선을 선택할 때마다 find와 union 연산을 수행하는 것입니다.
이 연산의 시간 복잡도는 O(E α(V))입니다. 여기서 α는 아커만 함수의 역함수로, 매우 느리게 증가하는 함수입니다. 

사실상 이 값은 거의 상수에 가깝습니다.

이제 이 연산을 간선 뿐 아니라 정점에도 사용하면 정점 갯수만큼 더해준 값에 아커만 곱해주면 되겠죠?

따라서 정리해보면

O( (V + E) α(|V|) ) + O(E log E) 이 나오게 됩니다.

|E| ≤ |V|² : 간선의 수는 정점의 수의 제곱 이하입니다.

즉, 완전 그래프의 경우 모든 정점이 서로 연결되므로 최대 간선 수는 |V|²입니다.

|E|가 |V|² 이하이므로, 양변에 로그를 취하면 lg |E| ≤ lg (|V|²) = 2 lg |V|가 됩니다.

 lg |E|는 O(lg |V|)와 같고, 이는 O(lg E)로 표현할 수 있습니다.

|E| ≥ |V| − 1 : 간선을 다 연결하면 노드에서 1 빼주면 간선의 수가 나옵니다.

연결 그래프에서 |E|가 |V| - 1 이상이므로, 전체 시간 복잡도는 O(E α(V)) + O(E log E)로 표현됩니다.

O(Eα(|V|)) + O(E logE) 에서 아커만 함수는 거의 상우에 가깝기 때문에 생략해도 됩니다.
따라서, O(E log E): 전체 시간 복잡도는 간선의 수에 따라 로그 시간 복잡도를 가집니다.

하지만 위에서 말했듯이 log |E|는 O log|V|와 같다고 했죠?

그래서 O(E log V) 로 표현해도 맞긴합니다.

어쨋든 크루스칼 알고리즘의 실행 시간 시간 복잡도는 간선의 수에 따라

O ( E log E) 입니다.

최소 신장 트리(MST)를 이해하면 두 가지 주요 알고리즘인 크루스칼 알고리즘과 프림 알고리즘을 효과적으로 적용할 수 있습니다. 

문제 정의

한 마을에는 집과 도로가 있습니다.
각 도로는 두개의 집만 연결합니다.
두 집 House u와 House v를 연결하는 도로의 수리 비용은 w(u,v)입니다. 

목표

모든 집이 서로 연결되도록 충분한 도로를 수리하되, 수리 비용이 최소가 되도록 해야 합니다.
즉, 모든 집이 서로 도달 가능해야 하며, 총 수리 비용이 최소화되어야 합니다.

그래프 정의

• 비방향 그래프 G=(V,E)로 구성되어 있습니다.
• V: 정점(집)
• E: 간선(도로)

각 간선 (u,v)에 대해 가중치 w(u,v)가 정의되어 있습니다. 

이는 도로의 수리 비용을 나타냅니다.

목표

T⊆E 를 찾아야 합니다.
1. T는 모든 정점을 연결해야 하며, T는 신장 트리(spanning tree)입니다.
2.

이 식이 최소화되어야 합니다. 

즉, 선택된 간선(u, v)쌍의 총 가중치(비용)가 최소가 되어야 합니다.

정리하자면 모든 신장 트리 중에서 가중치가 최소인 신장 트리를 최소 신장 트리(MST)라고 합니다.

예시

사진에 보시다시피 회색으로 칠해진 간선들은 모든 정점을 연결하면서도 총 가중치가 최소인 간선들입니다.

이 간선들이 바로 Minimum Spanning Tree, 즉 MST입니다.

하나의 그래프에 여러 개의 MST가 존재할 수 있습니다.

예를 들어, MST 간선 (e,f)를 그냥 간선 (c,e)로 교체하면, 새로운 다른 신장 트리 MST`가 생성되지만 가중치는 동일합니다.

MST의 속성

간선 수: MST는 | V | − 1개의 간선을 가집니다. (여기서 |V|는 정점의 수), 트리이기 때문에 간단히 생각하면됩니다.

즉, 모든 정점을 연결하면서도 최소한의 간선만 사용합니다. 

사이클 없음: MST는 사이클을 포함하지 않습니다. No Cycle.

비방향이기 때문에 사이클이 존재할 수가 없습니다.

유일하지 않을 수 있음: MST는 여러 개 존재할 수 있습니다. 다른 MST`가 존재가능한거죠.

MST 구하는 법

1. 간선의 집합 A를 구축합니다. 처음에는 A에 간선이 없습니다.

2. 루프 불변 조건: 반복문으로 간선을 A에 추가할 때마다 "A는 어떤 MST의 부분 집합이다"라는 조건을 유지해야 합니다.

즉, 추가하는 간선이 MST의 일부가 될 수 있어야 합니다. 루프 불변이니 반복문의 참인 조건이죠.
3. 간선 (u,v)가 A에 추가될 때, A가 어떤 MST의 부분 집합이여야합니다. 이를 위해 안전한 간선만 추가합니다. 

즉, 이 과정을 정리한 식은 A∪{(u,v)}인데, 이 집합 A가 어떤 MST의 부분 집합이 되어야 한단겁니다.

MST 구하는 의사 코드

입력: 인자로 각각 그래프 G와 각 간선의 가중치 w를 받습니다.
출력: 최소 신장 트리 A

과정을 보자면

초기화: A를 빈 집합으로 설정합니다.
반복문: A가 신장 트리가 아닐 때까지 반복합니다. 안전한 간선(u, v)을 찾아서 A에 추가합니다.
결과 반환: 최종적으로 A를 반환합니다.

몇가지 개념 정의

S ⊂ V, A ⊆ E라고 가정하도록합시다.

Cut : 그래프의 집합 V를 S 집합과 V−S 집합으로 정점을 나누는 파티션입니다.

사진에서는 그냥 반으로 S 집합과 V - S 집합으로 나눴습니다.

Cross : 간선 (u,v)가 컷 (S, V−S)를 교차한다고 할 때,

u의 한 끝점이 S에 있고, 다른 끝점 v가 V−S에 있을 때 그 간선이 크로스하고 있다고 합니다.

사진에서는 파란선들이 Cut에 덮여있으니 이 간선들이 Cross입니다.

Respects : 컷이 집합 A를 존중한다고 할 때, A의 어떤 간선도 컷을 교차하지 않는 경우를 의미합니다.

다시 말하자면 안전한 간선이란 MST에 포함가능한 간선입니다.

즉, 모든 간선 중에서 가중치가 가장 낮은 간선입니다.

그리고 집합 A에 들어가는 간선들은 모두 안전한 간선들만 들어갑니다.

이 때 집합 A의 간선들이 Cross 하는 간선들이 아니라면 컷이 집합 A를 존중한다고 하는겁니다.

이게 왜 필요하냐면 컷을 나누는 과정에서 집합 A의 간선이 포함되지 않도록 하는 조건을 위해섭니다. 

Light Edge : 컷을 교차하는 간선 중에서 가중치가 최소인 간선을 의미합니다. 

즉, 주어진 컷을 교차하는 모든 간선 중에서 가장 가벼운 간선입니다. 하나의 컷에 여러 Light Edge가 존재 가능합니다.

Respects와 다르게 컷을 교차하는, 즉 컷을 지나는 간선만 해당됩니다. 그중에서 가중치가 가장 낮은 간선이죠.

위 이미지에서의 세 파란 Cross 간선 중 왼쪽부터 3 6 1이라면 가장 오른쪽의 파란 cross 간선이 Light Edge,

이미지처럼 1 6 1이라면 두 1 간선들이 모두 Light Edge입니다.

이 Light Edge는 굉장히 중요합니다. 반복적으로 Light Edge만 찾다보면 MST가 완성되기 때문입니다.

아래 중심 정리에서 설명드리겠습니다.

중심정리 Central Theorem

1. 집합 A가 어떤 MST의 부분 집합이라고 가정합니다.
2. (S, V−S)는 집합 A를 존중하는 컷입니다.
3. (u, v)는 컷 (S, V−S)를 가로지르는 라이트 엣지입니다.
4. 그러면 (u, v)는 집합 A에 대해 안전한 간선입니다.

증명 과정

이 중심정리를 한번 정리해봅시다. (u,v)가 안전한 간선이라는 것을 보여주는 것이 목표입니다.

T를 집합 A를 포함하는 MST라고 가정합니다.
(a) 만약 T가 (u,v)를 포함한다면, 증명이 완료됩니다.

(u, v)가 안전한 간선이니까 MST에 포함되는겁니다.
(b) 만약 T가 (u,v)를 포함하지 않는다면, 이제 좀 어려워집니다.

방식은 A와 {(u,v)}를 포함하는 다른 MST′ 를 구성하는겁니다.

일단 b의 상황을 봅시다.

트리에서는 각 정점 쌍 사이에 유일한 경로가 존재합니다. 즉, 두 정점 u와 v 사이에는 오직 하나의 경로만 있습니다.

지금 사진엔 u와 v 사이가 실선으로 되어있는데 아직은 u와 v가 연결안되어있어요. 간선 (u, v)는 연결안되어있습니다.

T가 MST이므로, u와 v 사이에 유일한 경로 p가 존재합니다. 

이 경로는 컷 (S, V−S)를 최소한 한 번은 가로질러야 합니다.

경로라는게 중요합니다. 여러 간선들이 구성되는 경로입니다.

경로 p의 엣지 중 하나를 (x, y)라고 할 때, 이 엣지는 컷을 가로지릅니다. 사진에서는 회색선에 진한 검은색 선 보이시죠?

(u, v)를 선택할 때, 이 엣지의 가중치는 w(u, v)로 표현됩니다. 그리고 (x, y)의 가중치는 w(x, y)로 표현됩니다.
따라서, w(u, v) ≤ w(x, y)가 성립해야 합니다. 이는 (u, v)가 라이트 엣지라는 정의와 일치합니다.

웬 대소비교가 나오냐면 우리가 지금 MST를 찾아내야하기 때문에 u와 v의 간선은 무조건 가중치가 젤 낮겠죠?

만약 w(u, v)가 더 크다면 굳이 이걸 고를 필요없이 (x, y)을 골랐겠죠.

컷이 집합 A를 존중하므로, 엣지 (x, y)는 집합 A에 포함되지 않습니다.

즉, (x, y)는 컷을 가로지르지만, 집합 A에는 속하지 않는 간선입니다.

이번엔 아까 말했던 새로운 트리 T' 를 만들어봅시다.

우선 기존 MST T에서 (x, y)를 제거하여 두 개의 컴포넌트로 나눕니다.

그런 다음, 간선 (u, v)를 추가하여 두 컴포넌트를 다시 연결합니다.

이 때 기존 MST w(T) ≥ MST w(T)' 가 만족됩니다.

왜냐면 w(u, v) ≤ w(x, y)가 성립되기 때문에 우린 u, v를 라이트 엣지로 설정했으니까

당연히 기존 (x, y) 간선을 연결한 w(T)가 더 크거나 같은거죠. 증명 끝.

이제 이 공식을 봅시다.

새로운 MST T'는 기존 T 에서 (x, y) 간선을 빼기, 즉 제거한 뒤 (u, v)를 합집합, 즉 (u, v)를 추가한겁니다.

결국 T′ 는 스패닝 트리입니다. 모든 정점을 포함하고 연결되어 있기 때문입니다.

가중치 공식도 봅시다.

새로운 MST T'는 기존 T의 가중치 - 간선(x, y)을 제거했으니 가중치를 빼줍니다.

그리고 새로운 간선 w(u, v)를 추가했으니 가중치를 더해줍니다.

이 가중치의 결과물이 바로 MST T'의 가중치입니다.

w(T') ≤ w(T)는 위에 증명에서 말했듯이 라이트 엣지 때문에 무조건 라이트 엣지 (u, v)를 가진 T' 가 더 작거나 같습니다.

마지막으로 (u, v)가 집합 A에 대해 안전한 간선임을 보여야 합니다.

집합 A가 기존 MST T에 포함되고, 간선 (x, y)가 A에 포함되지 않으므로, A는 새로운 MST T′에도 포함됩니다.

그리고 A와 (u, v)를 합친 집합이 새로운 MST T′ 에 포함됩니다.

새로운 MST T′ 가 MST이므로, (u, v)는 안전한 간선으로 인정받습니다.

즉, (u, v)가 MST에 포함될 수 있음을 의미합니다.

부록

C는 그래프 G 𝐴 의 연결된 컴포넌트를 나타냅니다. 

여기서 G 𝐴 는 정점 집합 V와 간선 집합 A로 구성된 그래프입니다.

만약 (u, v)가 컴포넌트 C와 G 𝐴 의 다른 컴포넌트와 연결되는 라이트 엣지라면, 컷 (V𝐶, V − V𝐶)를 가로지르는 간선일겁니다. 

이 때 (u, v)는 집합 A에 대해 안전하다는 것입니다.

즉, 이 간선은 MST에 포함될 수 있습니다.

갑자기 든 생각이지만 만약 Minimum Spanning Tree가 아닌 Maximum Spanning Tree를 구하려고 하면 어떻게 될까요?

Light Edge : 컷을 교차하는 간선 중에서 가중치가 최소인 간선을 의미합니다. 

이 정의를 거꾸로 해서 최소가 아닌 최대인 간선을 찾는것으로 바꾸면 다 반대가 되기 때문에 구할 수 있겠죠?

어쨋든 오늘 알아본 MST의 아이디어로 뒤에 설명할 Kruskal Algorithm에 사용됩니다. 다음 포스팅에 다시 다뤄봅시다.

Strongly Connected Components, 줄여서 SCC라고 부릅니다.

강한 결합 요소 즉, SCC란 방향 그래프 G = ( V, E )에서 강하게 연결된 요소(SCC)는 그래프의 정점 집합 C ⊆ V 로,

이 집합의 모든 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u가는 경로가 존재하는 최대 집합입니다.

뭔말인가요

C ⊆ V 는 C가 SCC랑 같은데, 이 SCC들이 V의 부분집합이어야한다는 말입니다.

즉 그래프의 정점들 중 일부로 구성된다는 것을 의미합니다. 

u에서 v로 가는 경로와 v에서 u가는 경로가 존재한다는 말은 서로 상호 연결되서 u에서 v로 가고 v에서 u로 간다는 말입니다.

정점이 서로 도달 가능해야 강하게 연결된 요소,즉 SCC로 인정받을 수 있습니다.

최대 집합 또한 나오는데, "Maximal Set"이라는 용어로 해당 집합이 더 이상 다른 요소를 추가할 수 없는 상태라는 말입니다.

즉, 이 집합에 포함된 정점들끼리는 서로 연결되어 있지만, 다른 정점을 추가하면 연결성이 깨지게 됩니다.

말이 너무 어려운데 예시를 봅시다.

14 / 19 막 이런식으로 적혀있습니다만 이는 각각 시작 시간과 종료 시간인걸 보면 DFS가 된 그래프인걸 알 수 있죠?

DFS가 뭔지 모르시겠다면 아래 포스팅 보시면 됩니다.

https://kimyir.tistory.com/130

그리고 여기서 그룹으로 나눠서 테두리를 그려놨는데 이게 바로 SCC들입니다.

SCC 각각 보시면 서로 화살표로 상호연결되어있어 정점들끼리 가는 길이 존재합니다.

이걸 어렵게 말해서 집합 C에서 u와 v가 있다면 u~>v, v~>u로 가는 path가 있다고 합니다.

반대로 13/20에서 2/5로는 가지는데 2/5에서 13/20으로 가는길이 없는 경우는 서로 같은 SCC로 안묶이는걸 볼 수 있습니다.

각각 자기들끼리 연결되있는 상태에서 다른 정점을 추가하면 연결성이 끊어지기 때문에 각각 maximal한 상태,

즉 최대집합 상태입니다.

방향 그래프의 전치(Transpose) 형태

방향 그래프의 전치(Transpose) 형태,

즉 Transposed Form Of Directed Graph란 원래 그래프 G의 모든 간선의 방향을 반대로 뒤집은 것입니다.

간선의 방향이 뒤집어진 그래프 G^T 는 아래와 같이 정의됩니다.

이 그래프의 E^T 는 아래와 같습니다.

식이 이해가 안되는데 순서대로 설명하자면 E^T 간선 집합들이 중괄호 { 안에 들어가는 모든 쌍(u, v)를 포함한다는 말입니다.

이 모든 u에서 v로 가는 간선 쌍 (u, v)들에 대해서,

중간에 있는 : 기호는 "다음 조건을 만족하는" 이라는 의미입니다.

뒤에 (v, u) ∈ E는 원래 그래프 G 의 간선 집합 E에 (v, u)라는 간선이 존재한다는 의미입니다.  

결론

E^T = {(u, v) : (v, u) ∈ E}는 "전치 그래프 G^T의 간선 집합 E^T는 원래 그래프 G의 간선 집합 E에서 (v, u)가 존재하는 모든 (u, v)쌍으로 구성된다"는 의미입니다.

원래 그래프 G와 전치 그래프 G^T는 동일한 강하게 연결된 요소(SCC)를 가집니다.
즉, 정점 u와 v가 G에서 서로 도달 가능하다면, G^T에서도 서로 도달 가능하다는 것을 의미합니다.

시간 복잡도 

전치 그래프 G^T 는 인접 리스트를 사용하여 
Θ( 𝑉 + 𝐸 ) 시간에 생성할 수 있습니다. 

여기서 𝑉 는 정점의 수, 𝐸는 간선의 수를 의미합니다.

인접 리스트는 각 정점에 대해 그 정점과 연결된 다른 정점들의 리스트를 유지하는 데이터 구조입니다.

각 정점과 그에 연결된 간선을 모두 한 번씩 방문해야 하므로, 총 시간 복잡도는 정점 수와 간선 수의 합으로 표현됩니다.

컴포넌트 그래프 Component Graph 

Strongly Connected Components에서 그룹들을 G^SCC, Component의 그래프로 부릅니다.

V^SCC = 각 SCC는 그래프의 정점으로 표현됩니다.

즉, 원래 그래프의 각 강하게 연결된 요소는 구성 그래프에서 하나의 정점으로 나타납니다.

E^SCC = 원래 그래프 G에서 두 SCC 간에 간선이 존재하면,

구성 그래프 G^SCC에서도 해당 SCC간에 간선이 추가됩니다.

SCC 그래프 예시

왼쪽 오른쪽 설명 모두 동일합니다.

다만 그냥 초점에 따라 다르게 설명한것뿐입니다.

전치 그래프  G^T에서 DFS를 수행할 때, 원래 그래프 G에서의 종료 시간에 따라 정점을 내림차순으로 방문하기 때문에 오른쪽 이미지에서 검은색 애들(종료순서)을 따라서 가라는거랑 같은 말입니다.

어쨋든 저 과정을 다시 한글로 옮겨보면 

1. DFS(G) 호출:
원래 그래프 G에 대해 깊이 우선 탐색(DFS)을 수행하여 각 정점 u의 종료 시간을 f[u]로 기록합니다.
2. 전치 그래프 G^T 계산:

원래 그래프 G의 전치 그래프 G^T를 생성합니다. 전치 그래프는 모든 간선의 방향을 반대로 뒤집은 그래프입니다.
3. DFS(G^T) 호출:

전치 그래프 G^T에서 DFS를 수행합니다. 

이때, 첫 번째 DFS에서 기록한 종료 시간을 기준으로 정점을 내림차순으로 방문합니다. 즉, 

종료 시간이 높은 정점부터 낮은 정점 순으로 탐색합니다.
4. 출력:
두 번째 DFS에서 형성된 각 깊이 우선 탐색 트리의 정점들을 별도의 강하게 연결된 요소(SCC)로 출력합니다. 

각 트리는 하나의 SCC를 나타냅니다.

G^SCC는 DAG다 Lemma

G^SCC는 DAG입니다. 즉, 구성 그래프는 방향성이 있으며, 사이클이 없는 그래프라는 의미입니다.

만약 v′ 에서 v로 가는 경로가 존재한다면, u, u′, v, v′ 를 포함하는 사이클이 형성됩니다. 
이는 DAG의 정의에 어긋납니다.

다이어그램을 그려보면, v′ 에서 v로 가는 경로를 추가하면 u, u′, v, v′ 를 포함하는 원이 생긴다는 것입니다. 

이는 사이클을 의미합니다.

SCC 정확성 증명

어떻게 SCC가 정확하단걸 증명할 수 있을까요?

아이디어는 다음과 같습니다.

두 번째 DFS에서 첫 번째 DFS의 종료 시간을 기준으로 내림차순으로 정점을 고려함으로써, 

구성 그래프의 정점들을 위상 정렬(topological sort) 순서로 방문하고 있다는 것입니다. 

즉, SCC를 찾는 과정이 올바르게 진행되고 있음을 나타냅니다

이 과정이 잘 작동하는지 증명하기 위해 두 가지 표기법 문제를 다루어야 합니다.

d[u]와 f[u]에 대해 논의할 때, 항상 첫 번째 DFS에 대한 값을 참조해야 한다는 점을 강조합니다.

즉, 두 번째 DFS를 수행할 때 이 값들을 참조해야 한다는 것입니다.

d(U): 집합 U에 속하는 정점들 중에서 가장 이른 발견 시간을 나타냅니다. 

즉, U에 속하는 정점들 중에서 가장 먼저 방문된 정점의 발견 시간을 의미합니다.

f(U): 집합 U에 속하는 정점들 중에서 가장 늦게 종료된 시간을 나타냅니다.

즉, U에 속하는 정점들 중에서 가장 마지막에 탐색이 완료된 정점의 종료 시간을 의미합니다.

Lemma

C와 C ′는 그래프 G에서 서로 다른 강하게 연결된 요소(SCC)입니다.

만약 (u,v)라는 간선이 존재하고, u는 C에 속하며 v는 C′ 에 속한다고 가정합니다.

그러면 이런 그림이 나옵니다.

이 경우, f(C)>f(C′)라는 관계가 성립합니다. 

즉, SCC C의 종료 시간은 SCC C′ 의 종료 시간보다 더 큽니다. 더 늦게 끝난다는거죠.

이 Lemma의 증명

(u, v) ∈ E^T 는 (v, u)∈E를 의미합니다.

즉, G와 전치그래프 G^T의 SCC는 동일하므로 f(C)>f(C′)가 성립합니다.

첫 번째 결과: 만약 C에서 C′로 가는 간선이 있다면,

C의 종료 시간이 C′ 보다 작아야 한다는 것을 의미합니다. 

이는 탐색 순서와 종료 시간의 관계를 반영합니다.

두 번째 결과: 만약 C의 종료 시간이 C′ 보다 크다면, 

C에서 C′ 로 가는 간선이 존재할 수 없다는 것입니다.

전치 그래프 G^T에서 두 번째 DFS를 수행할 때, 종료 시간이 최대인 SCC C에서 시작합니다.

즉, f(C)가 가장 큰 SCC를 선택합니다.

두 번째 DFS는 SCC C의 어떤 정점 x에서 시작하며, 이 정점에서 시작하여 C에 속하는 모든 정점을 방문합니다.

부수적 결과에 따르면, f(C)>f(C′)인 모든 다른 SCC C′ 에 대해 G^T에서 C에서 C′로 가는 간선이 존재하지 않습니다.

따라서, 두 번째 DFS는 오직 C에 속하는 정점만 방문하게 됩니다. 

이는 DFS가 x에서 시작할 때, 깊이 우선 탐색 트리가 C의 정점들로만 구성된다는 것을 의미합니다.