크러스컬 알고리즘

위키백과, 우리 모두의 백과사전.
(크루스칼 알고리즘에서 넘어옴)
이동: 둘러보기, 검색

컴퓨터 과학에서, 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 {\color{Blue}O}(E \log V)의 시간복잡도를 가진다.

개요[편집]

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

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

알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 생성나무만을 가지게 된다.

시간 복잡도[편집]

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

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

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

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

예제[편집]

Prim Algorithm 0.svg 우리가 풀어야 할 그래프이다. 변 옆에 있는 숫자는 변의 가중치를 가리킨다.

지금은 모든 변들이 색이 동일하다.

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

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

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

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

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

정확성 증명[편집]

P를 연결 가중 그래프라 하고, Y를 크러스컬 알고리즘을 사용하여 생성된 P부분그래프라고 가정하자. Y순환을 가질 수 없다. 마지막 변이 하나 추가되어 순환을 생성한 것이라면, 그 마지막 변은 서로 다른 나무 사이에 존재할 수 없으며, 한 부분나무 속에 존재해야만 하기 때문이다. (순환을 만들려면 각 꼭짓점들이 한 부분나무 속에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 변을 만들 수 없다는 뜻이다.) Y는 비연결 그래프일 수 없다. Y 내에 또다른 연결 성분이 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 변이 추가되었을 것이기 때문이다. 결론을 내리면, YP생성나무이다.

다음으로는 생성나무 Y가 최소 생성나무(minimum spanning tree)임을 보이겠다.

Y_1이 최소 생성나무라고 가정하자. 만약 Y=Y_1이면 Y도 최소 생성나무가 된다. 이게 사실이 아니라고 가정하자. eY에는 있으나 Y_1에는 없는 변이라고 가정하자. Y_1 \cup {e}순환을 가질 수밖에 없다. 생성나무에 변을 하나 더하면 더 이상 생성나무가 아니기 때문이다. 이 순환은 다른 하나의 변f를 가지는데, feY에 추가되는 알고리즘의 단계에서 고려 안 된 변일 수밖에 없다. 안 그랬다면 e는 같은 나무의 다른 가지(branch)들을 서로 연결했을 것이고, 서로 다른 나무들은 연결시키지 않았을 것이기 때문이다. 그러므로Y_2=Y_1 \cup {e} \setminus {f}도 역시 생성나무이다. 이 생성나무의 총 가중치 합(total weight)은 Y_1의 총 가중치보다 작다. 그 까닭은 w(e) \leq w(f)이므로 알고리즘이 f를 방문하기 전에 e를 먼저 방문했기 때문일 것이다. 만약 가중치들이 같았다면, 우리는 Y에는 있으나 Y_1에는 없는 변 e를 생각할 수 있다. 만약 남아 있는 변이 없었다면, YY_1가 서로 다른 변들로 구성되어 있었더라도 Y의 총 가중치 합이 Y_1의 총 가중치 합과 같을 것이다. 이 때도 역시 Y는 최소 생성나무가 된다. 만약 Y_2의 총 가중치 합이 Y_1의 총 가중치 합보다 작은 경우에는, Y_1이 최소 생성나무가 아니라는 결론에 다다르게 된다. 이것은 w(e) < w(f)인 변 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

참고 문헌[편집]

같이 보기[편집]

바깥 고리[편집]