[Algorithms] Kruskal's Algorithm | 크루스칼 알고리즘

Kruskal's Algorithm

크루스칼 알고리즘

- Graph상에서 Minimum Spanning Tree(최소 신장 트리)를 구성하는 방법 중 하나이다.
- Weight값이 가장 작은 간선(=Light Edge; 경량 간선)들을 집합에 포함시켜 가면서 신장 트리를 구성한다.
- 이 때, 선택한 간선으로 인해 Cycle이 생긴다면, 해당 간선은 집합에 포함시키지 않는다.
- \(n\)개의 정점으로 최소 신장 트리를 구성한다면,
  Kruskal's 알고리즘에서는 \(n-1\)개의 간선을 선택할 때 까지 연산을 진행해야 한다.
- \(n\)개의 정점들을 모두 노드가 하나인 개별적인 트리로 본다면,
  Kruskal's 알고리즘에서는 \(n\)개의 트리로 구성된 Forest에서 두 트리를 하나로 합쳐가며
  하나의 트리로 만들어나가는 과정을 수행한다. 

* Prim's 알고리즘은 하나의 집합에 정점을 더해가며 하나의 신장트리를 만드는 방식이고,
  Kruskal's 알고리즘은 여러 집합을 합쳐가며 하나의 신장트리를 만드는 방식이다.

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

---

Mechanism (원리)

Phase	Description
(a)	- 주어진 그래프의 모습이다.
(b)	- 주어진 그래프에서 Weight의 최솟값은 5이다. - 해당 간선에 결부된 두 정점을 하나의 집합으로 합친다.   (두 정점은 각자의 집합을 이루고 있다가, 한 집합으로 합쳐지게 된다.)
(c)	- 현재, 그래프에서 Weight의 최솟값은 7이다. - 해당 간선에 결부된 두 정점을 하나의 집합으로 합친다.
(d)	- 현재, 그래프에서 Weight의 최솟값은 8이지만, 이러한 간선이 3개가 있다. - 3개의 최소 Weight Edge 중 하나를 임의로 선택하고,   그에 결부된 두 정점을 하나의 집합으로 합친다.
(e)	- 현재, 그래프에서 Weight의 최솟값은 8이지만, 이러한 간선이 2개가 있다. - 2개의 최소 Weight Edge 중 하나를 임의로 선택하고,   그에 결부된 두 정점을 하나의 집합으로 합친다.
(f)	- 현재, 그래프에서 Weight의 최솟값은 8이지만,   이 간선에 결부된 두 정점은 같은 집합에 속해있다. - 이 간선을 합치게 되면, Cycle이 형성되므로, 이 간선은 폐기한다.
(g)	- 현재, 그래프에서 Weight의 최솟값은 9이며,   이 간선에 결부된 두 정점은 서로 다른 집합에 속해있다. - 그러므로, 이 간선에 결부된 두 집합을 합쳐도 Cycle이 형성되지 않으므로,   두 집합을 합친다.
(h)	- 현재, 그래프에서 Weight의 최솟값은 11이며,   이 간선에 결부된 두 정점은 서로 다른 집합에 속해있다. - 그러므로, 이 간선에 결부된 두 집합을 합쳐도 Cycle이 형성되지 않으므로,   두 집합을 합친다. - 여기까지, 6개(총 정점의 개수 - 1)의 간선을 서로 합쳤다.
(i)	- 6개의 간선들에 대한 합집합 연산을 완료했으므로, Kruskal's 알고리즘을 종료한다.

- Kruskal's 알고리즘에서는 Weight값이 작은 간선들부터 검사하므로,
  상당수의 간선을 보지 않고도 최소 신장 트리를 구성할 수 있다.

Example. Kruskal's Algorithm on an undirected graph

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

Kruskal(G)
// G = (V, E) : Given Graph
// T : Spanning Tree
{
    T = empty_set();
    for(v ∈ V)
        make_set(v);
        
    A[1...|E|] = sort_by_weight(E); // sort by ascending order
    
    while(|T| < n-1) {
        (u, v) = pop(A); // u, v = Vertices that compose the edge (u, v)
        if(find_set(u) ∩ find_set(v) == empty_set()) { // u and v are disjoint
            T = T ∪ {(u, v)};
            find_set(u) ∪ find_set(v);
        }
    }
}

---

Performance (성능)

* Union with Rank와 Find-Set with Path Compression을 이용한 Set Operation을 채택할 경우
Time Complexity : \(O(|E|\log |V|)\)

- \(\texttt{make_set()}\) 작업은 \(\Theta(|V|)\)에 수행된다.
- 간선들을 Weight를 기준으로 오름차순으로 정렬하는 작업(\(\texttt{sort_by_weight()}\))은
  \(O(|E|*\log |E|) = O(|E|\log |V|)\)에 수행된다.
- \(\texttt{while}\) Loop는 최소 \(|V|-1\)회, 최대 \(|E|\)회에 수행된다.
- \(\texttt{find_set()}\)과 Union(∪) 작업은 \(O(|E|)\)에 수행된다.
- 즉, Union with Rank와 Find-Set with Path Compression 방법을 이용하여
  \(\texttt{make_set()}\)은 \(|V|\)번, \(\texttt{find_set()}\)과 Union(∪)작업은 \(|E|\)번 이루어졌으므로,
  이 3가지 집합 연산의 총 수행 시간은 \(O((|V|+|E|)\log^* |V|)\)가 된다.
  (여기서, \(O(\log^* |V|)\)는 사실상 \(O(1)\)이므로, 사실상 수행 시간은 \(O(|V|+|E|)\)이다.)

- 즉, Kruskal's 알고리즘의 수행시간은 \(O(|E|\log |V| + |V| + |E|) = O(|E|\log |V|)\) 이다.
  (사실상, 간선들을 Weight를 기준으로 정렬하는 작업이 전체 시간을 결정짓는다.)

---

Verification (검증)

Theorem. Weighted Undirected Graph \(G = (V, E)\)의 Vertex들이
임의의 두 집합 \(S\)와 \(V-S\)로 나눠져있다할 때,
Edge \((u, v)\)가 \(S\)와 \(V-S\) 사이의 Lightest Cross Edge이면,
\((u, v)\)를 포함하는 Graph \(G\)의 Minimum Spanning Tree가 반드시 존재한다.

* Lightest Cross Edge (최소 교차 간선)
- 그래프의 정점들이 집합 \(S\)와 \(V-S\)로 나눠져있다 할 때,
  간선의 한 끝 정점은 \(S\)에, 다른 끝 정점은 \(V-S\)에 속해져 있는 경우,
  해당 간선을 교차 간선(Cross Edge)이라 하고,
  이러한 교차 간선들 중, Weight값이 가장 작은 간선을 최소 교차 간선이라 한다.

pf) 임의의 최소 신장 트리 \(T\)가 간선 \((u, v)\)를 포함하고 있지 않다 하자.
트리 \(T\)는 연결 그래프이므로, 정점 \(u\)에서 정점 \(v\)에 이르는 Path가 반드시 존재하고,
이는 정점 \(u\)에서 정점 \(v\)에 이르는 유일한 Path이다.
Path가 두 개 이상이라면, \(u\)와 \(v\)를 포함하는 Cycle이 만들어져 트리라 부를 수 없다.

이 Path는 집합 \(S\)에서 집합 \(V-S\)로 이르는 (또는 그 반대로) Path이므로,
이 Path상에는 \(S\)와 \(V-S\) 사이의 Cross Edge가 하나 이상 존재한다.
이러한 Cross Edge 중 하나를 \((x, y)\)라 하자.

아래 그림 중 (a)는 이러한 상황을 도식화해놓은 그림이다.
그림에서 실선으로 그려진 직선과 곡선은 최소 신장 트리 \(T\)를 구성하는 간선를 의미한다.
(화살표는 Path임을 의미하는 것이고, 곡선은 일련의 간선들을 하나로 표현한 것이다.)

이러한 상황에서, 트리 \(T\)에 간선 \((u, v)\)를 더하면 Cycle이 생성된다.
이 Cycle은 앞의 \(u \rightsquigarrow v\) Path에 간선 \((u, v)\)가 더해진 Cycle이다.

트리 \(T\)에서 간선 \((x, y)\)를 제거하고, \((u, v)\)를 포함시키면 다른 신장 트리 \(T^*\)가 생성된다.
(그림 (b)에 해당되는 상황이다.)

간선 \((u, v)\)가 \(S\)와 \(V-S\) 사이의 최소 교차 간선이므로, \(w(u, v) \leq w(x, y)\) 이다.
그러므로, 간선 \((x, y)\)를 제거하고, \((u, v)\)를 새로 넣은 신장 트리 \(T^*\)는 \(w(T^*) \leq w(T)\)를 만족한다.
(만일, \(w(u, v) < w(x, y)\)라면, \(w(T^*) < w(T)\)가 되어 \(T\)가 최소 신장 트리라는 조건에 모순이 생기므로,
이런일은 발생할 수 없다.)
(만약, \(w(u, v) = w(x, y)\)라면, \(w(T^*) = w(T)\)가 되어 \(T^*\) 또한 최소 신장 트리라 할 수 있다.)

즉, \((u, v)\)를 포함하고 있지 않은 최소 신장 트리가 존재한다면,
반드시 \((u, v)\)를 포함하는 최소 신장 트리로도 바꿀 수 있다. 

Prim's Algorithm에서는 이미 구성된 집합 \(S\)에서 최소 신장 트리에 \(V-S\) 사이를 연결하는 최소 간선을 더하므로,
알고리즘의 무결성이 증명되고,
Kruskal's Algorithm에서는 임의의 간선 \((u, v)\)를 더하는 시점에서
\((u, v)\)는 그때까지 고려되지 않은 모든 간선들 중 최소 간선이므로,
정점 \(u\)가 속한 집합이 \(S\)일 때, Kruskal's 알고리즘의 작동 원리 상, 간선 \((u, v)\)는 집합 \(S\)와 \(V-S\)의 최소 교차 간선이므로,
알고리즘의 무결성이 증명된다.

또한, Kruskal's 알고리즘이 다루는 Forest는 Matroid에 속하는데,
Matroid 이론의 관점에서도Kruskal's 알고리즘의 결과가 Optimal Solution임이 증명된다.

---

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

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