컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 , 꼭짓점의 개수를 라고 하면 이 알고리즘은 의 시간복잡도를 가진다. 개요[편집]크러스컬 알고리즘은 아래의 순서대로 작동한다.
알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래프만을 가지게 된다. 크러스컬 알고리즘의 다른 형태가 있다. 이것은 그래프에서 변을 제거하는 방식이다.
알고리즘[편집]를 변의 개수라 하고, 를 꼭짓점의 개수라고 하자. 크러스컬 알고리즘은 시간 안에 동작한다고 증명될 수 있다. 간단한 자료 구조가 쓰인다면 안에 동작한다. 이 동작 시간은 동일한데, 그 까닭은 다음과 같다: 이러한 시간 복잡도 한계는 다음과 같은 방법으로 도달할 수 있다. 변들을 그 가중치 순으로 시간 내에 정렬한다. 정렬을 함으로써, "집합 S로부터 최소 가중치를 갖는 변을 제거한다"는 동작이 상수 시간에 행해질 수 있게 된다. 서로소 집합 자료 구조(유니온 파인드: 결합과 검색)를 이용하여 어떤 꼭짓점이 어떤 콤포넌트(component)에 속하는 지 추적한다. 디스조인트-셋 찾기(find) 동작 두 번에 시간이 걸린다. 각 변이 각각 한 유니언(union) 안에 있다고 가정하면 말이다. 간단한 서로소 집합 자료 구조인 랭크에 의한 합집합을 사용하는 디스조인트-셋 숲(disjoint-set forest with union by rank)를 쓰더라도, 개의 동작이 시간 안에 행해진다. 그러므로 총 시간 복잡도는 가 된다. 변들이 이미 정렬되어 있거나 선형 시간(linear time, ) 안에 정렬될 수 있다면(예를 들어 카운팅 정렬, 기수 정렬), 크러스컬 알고리즘은 좀 더 고도의 서로소 집합 자료 구조를 사용할 수 있다. 이때 동작 시간 복잡도는 가 되는데, 여기서 는 아주 느리게 증가하는 단일-값 아커만 함수의 역함수를 말한다. 예제[편집]
정확성 증명[편집]를 연결 가중 그래프라 하고, 를 크러스컬 알고리즘을 사용하여 생성된 의 부분 그래프라고 가정하자. 는 순환을 가질 수 없다. 마지막 변이 하나 추가되어 순환을 생성한 것이라면, 그 마지막 변은 서로 다른 나무 사이에 존재할 수 없으며, 한 부분나무 속에 존재해야만 하기 때문이다. (순환을 만들려면 각 꼭짓점들이 한 부분나무 속에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 변을 만들 수 없다는 뜻이다.) 는 비연결 그래프일 수 없다. 내에 또다른 연결 성분이 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 변이 추가되었을 것이기 때문이다. 결론을 내리면, 는 의 신장 부분 그래프이다. 다음으로는 신장 부분 그래프 가 최소 신장 부분 그래프(minimum spanning tree)임을 보이겠다. 이 최소 신장 부분 그래프라고 가정하자. 만약 이면 도 최소 신장 부분 그래프가 된다. 이게 사실이 아니라고 가정하자. 가 에는 있으나 에는 없는 변이라고 가정하자. 는 순환을 가질 수밖에 없다. 신장 부분 그래프에 변을 하나 더하면 더 이상 신장 부분 그래프가 아니기 때문이다. 이 순환은 다른 하나의 변를 가지는데, 는 가 에 추가되는 알고리즘의 단계에서 고려 안 된 변일 수밖에 없다. 안 그랬다면 는 같은 나무의 다른 가지(branch)들을 서로 연결했을 것이고, 서로 다른 나무들은 연결시키지 않았을 것이기 때문이다. 그러므로도 역시 신장 부분 그래프이다. 이 신장 부분 그래프의 총 가중치 합(total weight)은 의 총 가중치보다 작다. 그 까닭은 이므로 알고리즘이 를 방문하기 전에 를 먼저 방문했기 때문일 것이다. 만약 가중치들이 같았다면, 우리는 에는 있으나 에는 없는 변 를 생각할 수 있다. 만약 남아 있는 변이 없었다면, 나 가 서로 다른 변들로 구성되어 있었더라도 의 총 가중치 합이 의 총 가중치 합과 같을 것이다. 이 때도 역시 는 최소 신장 부분 그래프가 된다. 만약 의 총 가중치 합이 의 총 가중치 합보다 작은 경우에는, 이 최소 신장 부분 그래프가 아니라는 결론에 다다르게 된다. 이것은 인 변 가 있다는 처음의 가정에 위배되게 된다. 결론적으로, 는 (과 변들도 같고, 가중치도 같은) 완전한 최소 신장 부분 그래프가 될 수밖에 없다. 크러스컬 알고리즘의 결과인 신장 부분 그래프 Y의 비용이 최소임을 보이는 다른 방법은 수학적 귀납법이다. 다음 명제가 참임을 수학적 귀납법으로 증명한다. "만약 F가 크러스컬 알고리즘의 각 단계에서 나타나는 변의 집합 중의 하나라고 하면 F를 포함하는 최소 생성나무가 있다." 이 명제를 증명하면 결국 크러스컬 알고리즘의 마지막 단계에 나타나는 생성나무 Y를 포함하는 최소 생성나무가 있고 Y가 곧 최소 생성나무이다.
크러스컬 알고리즘 다른 형태의 증명 나무에 관한 정리에서 n개의 꼭짓점을 가진 그래프가 연결 그래프일 때, 회로를 가지지 않는 것과 n-1개의 변을 가지는 것은 동일함이 알려져 있다. 알고리즘의 각 단계에서 얻는 그래프는 연결을 항상 유지하고 있으며 마지막 단계의 그래프는 n-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 edge 참고 문헌[편집]
같이 보기[편집]
각주[편집]
외부 링크[편집]
|