크러스컬 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

크러스컬 알고리즘(Kruskal's algorithm)은 최소 비용 신장 트리를 찾는 알고리즘이다. 간선의 개수를 E, 점의 개수를 V라고 하면 이 알고리즘은 {\color{Blue}O}(E \log V)의 시간복잡도를 가진다.

개요[편집]

크러스컬 알고리즘은 아래의 순서대로 작동한다.

  1. 그래프의 각 정점이 각각 하나의 트리가 되도록 하는 포레스트 F을 만든다.
  2. 모든 간선을 원소로 갖는 집합 S를 만든다.
  3. S가 비어있지 않는 동안
    1. 가장 작은 가중치의 간선을 S에서 하나 빼낸다.
    2. 그 간선이 어떤 두 개의 트리를 연결한다면 두 트리를 연결하여 하나의 트리로 만든다.
    3. 그렇지 않다면 그 간선은 버린다.

알고리즘이 종료됐을 때 포레스트 F는 하나의 최소 비용 신장 트리만을 가지게 된다.

시간 복잡도[편집]

E를 간선(edge)의 개수라 하고, V를 정점(vertice)의 개수라고 하자. 크러스컬 알고리즘은 {\color{Blue}O}(E \log V) 시간 안에 동작한다고 증명될 수 있다. 간단한 자료 구조가 쓰인다면 O(E \log V) 안에 동작한다. 이 동작 시간은 동일한데, 그 까닭은 다음과 같다:

  • E는 최대 V^2 개일 수 있다. \log V^2 = 2 \log VO(\log V)이다.
  • 홀로 떨어진 정점(vertices)들을 무시한다면 (그들 각각은 그만의 최소 비용 걸침 나무가 된다.), V \le 2E이다. 그러므로 \log VO(\log E)이다.

이러한 시간 복잡도 한계는 다음과 같은 방법으로 도달할 수 있다.: 간선(edge)들을 그들의 무게(weight) 순으로 O(E \log E) 시간 내에 정렬한다; 정렬을 함으로써, "집합 S로부터 최소 무게(weight)를 갖는 간선(edge)를 제거한다"는 동작이 상수(constant) 시간에 행해질 수 있게 된다. 디스조인트-셋 자료 구조(유니온 파인드: 결합과 검색)를 이용하여 어떤 정점(vertice)이 어떤 콤포넌트(component)에 속하는 지 추적한다. 디스조인트-셋 찾기(find) 동작 두 번에 O(E) 시간이 걸린다. 각 간선(edge)이 각각 한 유니언(union) 안에 있다고 가정하면 말이다. 간단한 디스조인트-셋 자료 구조인 랭크에 의한 합집합을 사용하는 디스조인트-셋 포레스트(disjoint-set forest with union by rank)를 쓰더라도, O(E) 개의 동작이 O(E \log V) 시간 안에 행해진다. 그러므로 총 시간 복잡도는 O(E \log E) = O(E \log V)가 된다.

간선(edge)들이 이미 정렬되어 있거나 선형 시간(linear time, O(E)) 안에 소트될 수 있다면(예를 들어 카운팅 정렬, 라딕스 정렬), 크러스컬 알고리즘은 좀 더 고도의 디스조인트-셋 자료 구조를 사용할 수 있다. 이때 동작 시간 복잡도는 O(E \alpha(V))가 되는데, 여기서 \alpha 는 아주 느리게 증가하는 단일-값 애커만 함수의 역함수를 말한다.

예제[편집]

Prim Algorithm 0.svg 우리가 풀어야 할 그래프이다. 간선(arc) 옆에 있는 숫자는 간선의 무게(weight)를 가리킨다.

지금은 모든 간선(arc)들이 색이 동일하다.

Kruskal Algorithm 1.svg ADCE 가 가장 짧은(weight가 가장 작은) 간선이다. 아무거나 골라서 AD를 선택한다. AD의 색을 변경하였다.
Kruskal Algorithm 2.svg 이제, CE가, 무게(weight)가 5로서, 루프(loop)를 생성하지 않는 가장 짧은 간선이다. CE의 색을 변경하였다.
Kruskal Algorithm 3.svg 같은 방식으로 고르면 다음 간선은 DF이다. 무게(weight)는 6이다.
Kruskal Algorithm 4.svg 다음으로 가장 짧은 간선은 ABBE인데, 둘 다 길이 (= 무게(weight))가 7이다. 임의로AB를 골랐다.

BD는 빨강색으로 변경하였는데, ABD를 연결시키면 루프를 이루기 때문이다.

Kruskal Algorithm 5.svg 다음으로 가장 짧은 간선은 BE로서 길이 7이다. 더 많은 간선들이 빨강으로 변했다. BCE 루프를 생성하기 때문에

BC가 빨강색으로 변했으며, DEBA 루프를 생성하기 때문에 DE가 빨강색으로 변했고,
FEBAD 루프를 생성하기 때문에 FE가 빨강색으로 변했다.

Kruskal Algorithm 6.svg 끝내, EG가 연결되면서 알고리즘이 종료된다. 최소 비용 신장 트리가 완성되었다.

정확성 증명[편집]

P를 정점들이 연결된(connected) 가중치(weighted) 그래프라 하고, Y를 크러스컬 알고리즘을 사용하여 생성된 P의 서브그래프라고 가정하자. Y는 순환고리(cycle)를 가질 수 없다. 마지막 간선(edge)이 하나 추가되어 순환고리를 생성한 것이라면, 그 마지막 간선(edge)은 서로 다른 트리 사이에 존재할 수 없으며, 한 서브트리 내에 존재해야만 하기 때문이다. (순환고리를 만들려면 각 정점들이 한 서브트리 내에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 간선(edge)을 만들 수 없다는 뜻이다.) Y는 연결 안 된(disconnected) 그래프일 수가 없다. Y 내에 연결 안 된 콤포넌트가 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 간선(edge)이 추가되었을 것이기 때문이다. 결론을 내리면, YP의 스패닝 트리이다.

다음으로는 스패닝 트리 Y가 최소신장트리(MST: Minimum Spanning Tree)임을 보이겠다.

Y_1이 MST라고 가정하자. 만약 Y=Y_1이면 Y도 MST가 된다. 이게 사실이 아니라고 가정하자. eY에는 있으나 Y_1에는 없는 간선(edge)이라고 가정하자. Y_1 \cup {e}는 순환고리(cycle)을 가질 수밖에 없다. 스패닝 트리에 간선을 하나 더하면 더 이상 스패닝 트리가 아니기 때문이다. 이 순환고리(cycle)는 다른 하나의 간선(edge) f를 가지는데, feY에 추가되는 알고리즘의 단계에서 고려 안 된 간선(edge)일 수밖에 없다. 안 그랬다면 e는 같은 트리의 다른 브랜치(branch)들을 서로 연결했을 것이고, 서로 다른 트리들은 연결시키지 않았을 것이기 때문이다. 그러므로Y_2=Y_1 \cup {e} \setminus {f}도 역시 스패닝 트리이다. 이 스패닝 트리의 총 무게 합(total weight)은 Y_1의 총 무게 합(total weight)보다 작다. 그 까닭은 w(e) \leq w(f)이므로 알고리즘이 f를 방문하기 전에 e를 먼저 방문했기 때문일 것이다. 만약 무게값(weight)들이 같았다면, 우리는 Y에는 있으나 Y_1에는 없는 간선(edge) e를 생각할 수 있다. 만약 남아 있는 간선(edge)이 없었다면, YY_1가 서로 다른 간선(edge)들로 구성되어 있었더라도 Y의 총 무게 합이 Y_1의 총 무게 합과 같을 것이다. 이 때도 역시 Y는 미니멈 스패닝 트리가 된다. 만약 Y_2의 총 무게 합이 Y_1의 총 무게 합보다 작은 경우에는, Y_1이 미니멈 스패닝 트리가 아니라는 결론에 다다르게 된다. 이것은 w(e) < w(f)인 간선(edge) e,f가 있다는 처음의 가정에 위배되게 된다. 결론적으로, Y는 (Y_1과 간선들도 같고, 무게도 같은) 완전한 미니멈 스패닝 트리가 될 수밖에 없다.

의사 코드[편집]

 1  function Kruskal(G)
 2    for each vertex v in G do
 3      Define an elementary cluster C(v) ← {v}.
 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
 5    Define a tree T ← Ø       //T will ultimately contain the edges of the MST
 6     // n is total number of vertices
 7    while T has fewer than n-1 edges do
 8      // edge u,v is the minimum weighted route from/to v
 9      (u,v) ← Q.removeMin()
10      // prevent cycles in T. add u,v only if T does not already contain an edge consisting of u and v. 
11      // Note that the cluster contains more than one vertex only if an edge containing a pair of
12      // the vertices has been added to the tree.
13      Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14      if C(v) ≠ C(u) then
15        Add edge (v,u) to T.
16        Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17    return tree T

참고 문헌[편집]

같이 보기[편집]

바깥 고리[편집]