크루스칼(Kruskal) 알고리즘

최초작성일 [2020.01.29]

크루스칼(Kruskal) 알고리즘은 그래프에서 최소신장트리(Minimum Spanning Tree)를 찾는 데 쓰이는 알고리즘이다.

1. 각 정점을 독립된 component으로 간주한다.

2. 탐색하지 않은 간선들 중에 가중치가 가장 작은 간선 e로 연결된 두 정점 v1, v2가 같은 connected component에 있는지 확인한다.

3. 같은 connected component에 있지 않으면 e를 집합 X에 추가하고 v1, v2를 같은 disjoint set으로 묶는다.

4. 같은 connected component에 있으면 e는 사이클을 만드는 간선이므로 X에 추가하지 않는다.

5. 모든 정점이 1개의 disjoint set으로 묶일 때까지 2 ~ 4 를 반복한다.

의사코드는 아래와 같다.

def kruskal(G):
  X = set()

  for each v in V:
    make_set(v)
  
  E = sort_E_by_weight(E)  # 1
 
  for each (v1, v2) in E:
    if find(v1) != find(v2):  # 2
      X.add((v1, v2))
      union(v1, v2)  # 3
  
  return X

시간복잡도

시간복잡도를 계산하기 위해 의사코드에서 매긴 번호로 로직을 분류한다.

1. 간선을 정렬하는 데 걸리는 시간복잡도는 퀵정렬을 사용한다면 O(|E|log|E|) 이다.

2. 각 간선을 순회하면서 find()를 2번 실행하므로 O(log|V|)이다. (트리형태의 disjoint set에서 어떤 노드의 루트를 찾는 데 걸리는 시간복잡도는 O(log|V|)이기 때문.)

3. union()은 heuristic rank를 적용하면 O(1)이다. (find()를 호출하면서 v1, v2의 루트가 이미 갱신되었기 때문.)

따라서 |E| * log|E| + |E|(log|V| + 1) = |E| * (log|E| + log|V|) 가 된다. 그런데 최신장트리는 모든 정점이 연결되어야 함을 가정하므로 그래프 내 간선의 갯수는 적어도 |V| - 1 개 이상이다. 따라서 크루스칼 알고리즘의 시간복잡도는 최종적으로

|E| * (log|E| + log(|E|+1)} = O(|E|log|E|) 가 된다.