크러스컬 알고리즘

3. 예제

그림	설명
	우리가 풀어야 할 그래프이다. 변 옆의 숫자는 가중치를 나타낸다. 지금은 모든 변의 색이 같다.
	AD 와 CE 가 가장 짧은(가중치가 가장 작은) 변이다. 아무거나 골라서 AD를 선택하고 색을 변경하였다.
	이제, CE가 가중치가 5로서, 고리(loop)를 생성하지 않는 가장 짧은 변이다. CE의 색을 변경하였다.
	같은 방식으로 고르면 다음 변은 DF이다. 가중치는 6이다.
	다음으로 가장 짧은 변은 AB와 BE인데, 둘 다 길이 (= 가중치)가 7이다. 임의로 AB를 골랐다. BD는 빨강색으로 변경하였는데, ABD를 연결시키면 루프를 이루기 때문이다.
	다음으로 가장 짧은 변은 BE로서 길이 7이다. 더 많은 변들이 빨강으로 변했다. BCE 루프를 생성하기 때문에 BC가 빨강색으로 변했으며, DEBA 루프를 생성하기 때문에 DE가 빨강색으로 변했고, FEBAD 고리를 생성하기 때문에 FE가 빨강색으로 변했다.
	끝내, EG가 연결되면서 알고리즘이 종료된다. 최소 비용 신장 부분 그래프가 완성되었다.

4. 정확성 증명

크러스컬 알고리즘의 정확성은 다음 두 가지 명제를 증명함으로써 보일 수 있다.

1. 크러스컬 알고리즘은 신장 트리를 생성한다.

2. 크러스컬 알고리즘으로 생성된 신장 트리는 최소 비용을 갖는다.

하위 섹션에서 각 명제에 대한 자세한 증명을 다루고 있으므로, 여기서는 간략하게 요약한다.
신장 트리 생성 증명: 알고리즘은 항상 서로 다른 두 개의 트리를 연결하는 변을 추가하므로 순환(사이클)이 생기지 않는다. 또한 모든 정점을 연결하는 변을 선택하므로, 결과 그래프는 모든 정점을 포함하는 연결된 그래프, 즉 신장 트리가 된다.
최소 비용 증명: 귀류법을 사용하여 증명한다. 크러스컬 알고리즘으로 생성된 신장 트리 $Y$가 최소 신장 트리가 아니라고 가정하고, $Y$와 가장 많은 변을 공유하는 다른 최소 신장 트리 $Y\_1$을 생각한다. $Y$에는 있지만 $Y\_1$에는 없는 변 $e$를 고려하여, $Y\_1$에 $e$를 추가하고 순환에서 다른 변 $f$를 제거하는 방식으로 $Y\_1$보다 $Y$와 더 많은 변을 공유하는 최소 신장 트리를 만들 수 있음을 보인다. 이는 $Y\_1$의 선택에 모순되므로, $Y$가 최소 신장 트리임을 알 수 있다.

이 외에도, 수학적 귀납법을 활용한 증명 방법이 존재한다.

4. 1. 신장 트리 생성 증명

• $Y$는 순환(cycle)을 가질 수 없다. 알고리즘에 의해 순환을 형성하는 변은 추가되지 않기 때문이다.
• $Y$는 비연결 그래프일 수 없다. $Y$에 연결되지 않은 부분이 있다면, 알고리즘에 의해 두 부분을 연결하는 변이 추가되었을 것이기 때문이다.

• 만약 $Y\; =\; Y\_1$이면, $Y$는 최소 신장 부분 그래프이다.
• $Y\; \backslash neq\; Y\_1$인 경우, $Y$에는 있지만 $Y\_1$에는 없는 변 $e$가 존재한다.
• $Y\_1\; \backslash cup\; \backslash \{e\backslash \}$는 순환을 포함한다. 신장 부분 그래프에 변을 추가하면 순환이 발생하기 때문이다.
• 이 순환에는 $Y$에 추가될 때 고려되지 않은 다른 변 $f$가 존재한다. 그렇지 않으면 $e$는 같은 나무의 다른 가지들을 연결하여 순환을 형성했을 것이기 때문이다.
• $Y\_2\; =\; Y\_1\; \backslash cup\; \backslash \{e\backslash \}\; \backslash setminus\; \backslash \{f\backslash \}$ 역시 신장 부분 그래프이다.
• $w(e)\; \backslash leq\; w(f)$이므로, $Y\_2$의 총 가중치는 $Y\_1$의 총 가중치보다 작거나 같다. 알고리즘은 $f$보다 $e$를 먼저 선택했기 때문이다.
• 만약 가중치가 같다면, $Y$와 $Y\_1$의 총 가중치는 같아지고, $Y$는 최소 신장 부분 그래프가 된다.
• $Y\_2$의 총 가중치가 $Y\_1$보다 작다면, $Y\_1$은 최소 신장 부분 그래프가 아니라는 결론에 도달한다. 이는 초기 가정에 위배된다.

• 기저 단계: 알고리즘 시작 단계에서 F는 공집합이다. 유한 그래프는 유한 개의 생성 트리를 가지며, 최소 생성 트리가 반드시 존재한다. 따라서 공집합 F를 포함하는 최소 생성 트리가 존재한다.
• 귀납 가정: 크러스컬 알고리즘의 특정 단계까지 변의 집합 F를 포함하는 최소 생성 트리 T가 존재한다고 가정한다.
• 귀납 단계: 다음 단계에서 추가되는 변을 $e$라고 하면, 다음 집합은 $F\; \backslash cup\; \backslash \{e\backslash \}$이다.
• $e$가 T의 변이면, $F\; \backslash cup\; \backslash \{e\backslash \}$를 포함하는 최소 생성 트리는 T이다.
• $e$가 T의 변이 아니면, $T\; \backslash cup\; \backslash \{e\backslash \}$에는 유일한 순환 C가 생긴다. F는 순환을 가질 수 없으므로, 순환 C에 포함되면서 F에는 없는 변 $f$가 존재한다.
• $T\; \backslash cup\; \backslash \{e\backslash \}\; -\; \backslash \{f\backslash \}$는 생성 트리이다.
• 크러스컬 알고리즘은 최소 가중치 변을 추가하므로, $w(e)\; \backslash leq\; w(f)$이다. 따라서 $T\; \backslash cup\; \backslash \{e\backslash \}\; -\; \backslash \{f\backslash \}$의 비용은 T의 비용 이하이다.
• $T\; \backslash cup\; \backslash \{e\backslash \}\; -\; \backslash \{f\backslash \}$는 $F\; \backslash cup\; \backslash \{e\backslash \}$를 포함하는 최소 생성 트리이다.

• 기저 단계: 알고리즘 시작 단계의 그래프는 모든 변을 포함하므로 최소 비용 생성 트리를 포함한다.
• 귀납 가정: 알고리즘의 n개 변이 남을 때까지 각 단계의 그래프가 최소 비용 생성 트리를 포함한다고 가정한다.
• 귀납 단계: n-1개 변이 남은 그래프(생성 트리)가 최소 비용 생성 트리를 포함함을 보인다.
• n개 변이 남은 그래프를 F, F가 포함하는 최소 비용 생성 트리를 T라고 하자.
• F에서 변 e를 제거하여 알고리즘이 종료된다고 하자.
• T는 n-1개 변을 가진다. F에서 변 f를 제거하면 T가 된다고 가정하자.
• 알고리즘은 최대 가중치 변을 제거하므로, $w(e)\; \backslash geq\; w(f)$이다.
• 따라서 F-e는 T의 비용 이하의 생성 트리이다. T는 최소 비용 생성 트리이므로, F-e는 T와 비용이 같고, 최소 비용 생성 트리이다.

4. 2. 최소 비용 증명

• ''F''가 비어 있을 때, 즉 처음에는 '''''P'''''가 분명히 참이다: 어떤 최소 신장 트리든 상관없으며, 가중 연결 그래프는 항상 최소 신장 트리를 가지므로 그러한 트리가 존재한다.
• 이제 '''''P'''''가 최종 간선 집합이 아닌 어떤 ''F''에 대해 참이라고 가정하고, ''T''를 ''F''를 포함하는 최소 신장 트리라고 하자.
• * 다음 선택된 간선 ''e''가 ''T''에도 포함되어 있다면, ''F'' + ''e''에 대해 '''''P'''''는 참이다.
• * 그렇지 않고, ''e''가 ''T''에 없다면, ''T'' + ''e''는 사이클 ''C''를 갖는다. 사이클 ''C''는 ''F'' + ''e''에 속하지 않는 간선을 포함하는데, 이는 ''e''가 ''F''에 추가될 때는 사이클을 형성하지 않지만 ''T''에서는 사이클을 형성하기 때문이다. ''f''를 ''C''에 속하지만 ''F'' + ''e''에는 속하지 않는 간선이라고 하자. ''f''는 ''T''에도 속하는데, 이는 ''f''가 ''T'' + ''e''에는 속하지만 ''F'' + ''e''에는 속하지 않기 때문이다. '''''P'''''에 의해, ''f''는 알고리즘에 의해 고려되지 않았다. 따라서 ''f''는 최소한 ''e''와 같은 가중치를 가져야 한다. 그러면 ''T'' − ''f'' + ''e''는 트리이며, ''T''와 같거나 더 작은 가중치를 갖는다. 그러나 ''T''가 최소 신장 트리이므로 ''T'' − ''f'' + ''e''는 ''T''와 같은 가중치를 가지며, 그렇지 않으면 모순이 발생하고 ''T''는 최소 신장 트리가 되지 못할 것이다. 따라서 ''T'' − ''f'' + ''e''는 ''F'' + ''e''를 포함하는 최소 신장 트리이며, 다시 '''''P'''''가 성립한다.
• 따라서, 귀납법의 원리에 의해, ''F''가 신장 트리가 되었을 때 '''''P'''''가 성립하며, 이는 ''F''가 자체가 최소 신장 트리일 때만 가능하다.

5. 의사 코드

다음은 분리 집합 자료구조를 사용하여 구현된 크러스컬 알고리즘의 의사 코드이다.

```

'''알고리즘''' 크루스칼(''G'') '''는'''

F := ∅

'''G.V에 있는 각''' v '''에 대해'''

MAKE-SET(v)

'''가중치({u, v})에 따라 정렬된 G.E의 각''' {u, v} '''에 대해, 오름차순으로'''

'''만약''' FIND-SET(u) ≠ FIND-SET(v) '''라면'''

F := F ∪ { {u, v} }

UNION(FIND-SET(u), FIND-SET(v))

'''반환''' F

```

위 코드는 숲 ''F''를 무방향 간선 집합으로 나타내며, 두 정점이 동일한 트리에 속하는지 효율적으로 확인하기 위해 분리 집합 자료구조를 사용한다.

크러스컬 알고리즘의 절차는 다음과 같다.

• 그래프의 각 정점이 각각의 트리에 속하도록 숲(트리의 집합) ''F''를 생성한다(즉, 정점 1개만으로 구성된 트리가 정점의 개수만큼 존재한다).
• ''S'' ← 그래프의 모든 변을 포함하는 집합
• while (''S''가 공집합이 아닐 때)
• ''S''에서 가중치가 최소인 변 ''e''를 제거한다.
• if (''e''가 두 트리를 연결하는 경우)
• ''e''를 숲에 추가하고 두 트리를 하나로 합친다.

6. 병렬 알고리즘

크루스칼 알고리즘은 본질적으로 순차적이어서 병렬화하기 어렵다. 그러나 가장자리(edge)의 초기 정렬을 병렬로 수행하거나, 각 반복에서 최소 가중치 가장자리를 추출하기 위해 이진 힙의 병렬 구현을 사용할 수 있다.^[5]

병렬 정렬은 $O(n)$ 시간 내에 $O(\log n)$개의 프로세서에서 가능하다는 점을 고려할 때,^[6] 크루스칼 알고리즘의 실행 시간은 $O(E \alpha(V))$로 줄어들 수 있다. 여기서 $\alpha$는 단일 값 아커만 함수의 역함수이다.

오시포프(Osipov) 등이 설명한 필터-크루스칼(Filter-Kruskal)이라는 크루스칼 알고리즘의 변형은 병렬화에 더 적합하다.^[7] 필터-크루스칼의 기본 아이디어는 퀵 정렬과 유사한 방식으로 가장자리를 분할하고 동일한 트리의 정점을 연결하는 가장자리를 필터링하여 정렬 비용을 줄이는 것이다. 다음은 필터-크루스칼 알고리즘의 의사 코드이다.

'''function''' filter_kruskal(G) '''is'''

    '''if''' |G.E| < kruskal_threshold:

        '''return''' kruskal(G)

    pivot = choose_random(G.E)

    E, E = partition(G.E, pivot)

    A = filter_kruskal(E)

    E = filter(E)

    A = A ∪ filter_kruskal(E)

    '''return''' A

'''function''' partition(E, pivot) '''is'''

    E = ∅, E = ∅

    '''foreach''' (u, v) in E '''do'''

        '''if''' weight(u, v) ≤ pivot '''then'''

            E = E ∪ {(u, v)}

        '''else'''

            E = E ∪ {(u, v)}

    '''return''' E, E

'''function''' filter(E) '''is'''

    E = ∅

    '''foreach''' (u, v) in E '''do'''

        '''if''' find_set(u) ≠ find_set(v) '''then'''

            E = E ∪ {(u, v)}

    '''return''' E

참조

_[1] 서적 Algorithm design https://www.worldcat[...] Pearson/Addison-Wesley 2006
_[2] 서적 Introduction To Algorithms https://archive.org/[...] MIT Press
_[3] 간행물 On the shortest spanning subtree of a graph and the traveling salesman problem
_[4] 간행물 Formal Procedures for connecting terminals with a minimum total wire length 1957-10
_[5] 간행물 Parallel graph algorithms 1984
_[6] 서적 Introduction to Parallel Computing Addison-Wesley
_[7] 간행물 The filter-kruskal minimum spanning tree algorithm 2009
_[8] 서적 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum http://tarjomefa.com[...] 2012
_[9] 서적 Transactions on Engineering Technologies 2014
_[10] 서적 자바로 배우는 쉬운 자료구조 2013-07-30