크루스 칼 알고리즘 ( Kruskal ' s algorithm ) 은 최소 비용 걸침 나무 를 찾 는 알고리즘 이 다 . 간선 의 개수 를 E , 점 의 개수 를 V 라고 하 면 이 알고리즘 은 O ( E log V ) 의 시간 복잡도 를 가진다 . 알고리즘 크루스 칼 알고리즘 은 아래 의 순서 대로 작동 한다 : 그래프 의 각 정점 이 각각 하나 의 트리 가 되 도록 하 는 포레스트 F 을 만든다 모든 간선 을 원소 로 갖 는 집합 S 를 만든다 S 가 비 어 있 지 않 는 동안 가장 작 은 가중치 의 간선 을 S 에서 하나 빼낸다 그 간선 이 어떠 두 개 의 트리 를 연결 한다면 두 트리 를 연결 하 여 하나 의 트리 로 만든 다 그렇 지 않 다면 그 간선 은 버린다 알고리즘 이 종료 됐 을 때 포레스트 F 는 하나 의 최소 비용 걸침 나무 만 을 가지 게 된다 . 시간 복잡도 E 를 간선 ( edge ) 의 개수 라 하 고 , V 를 정점 ( vertice ) 의 개수 라고 하 자 . 크루스 칼 알고리즘 은 O ( E log E ) 시간 안 에 동작 한다고 증명 될 수 있 다 . 간단 한 자료 구조 가 쓰인다면 O ( E log V ) 안 에 동작 한다 . 이 동작 시간 은 동일 한데 , 그 까닭 은 다음 과 같 다 : E 는 최대 V 2 개 일 수 있 다 . logV 2 = 2 logV 는 O ( log V ) 이 다 . 홀로 떨어진 정점 ( vertices ) 들 을 무시 한다면 ( 그 들 각각 은 그 만 의 최소 비용 걸침 나무 가 된다 . ) , V ≤ 2 E 이 다 . 그러므로 log V 는 O ( 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 α ( V ) ) 가 되 는데 , 여기 서 α 는 아주 느리 게 증가 하 는 단일 - 값 애커만 함수 의 역함수 를 말 한다 . 예 제 우리 가 풀 어야 할 그래프 이 다 . 간선 ( arc ) 옆 에 있 는 숫자 는 간선 의 무게 ( weight ) 를 가리킨다 . 지금 은 모든 간선 ( arc ) 들 이 색 이 동일 하 다 . AD 와 CE 가 가장 짧 은 ( weight 가 가장 작 은 ) 간선 이 다 . 아무거 나 골라서 AD 를 선택 한다 . AD 의 색 을 변경 하 였 다 . 이제 , CE 가 , 무게 ( weight ) 가 5 로서 , 루프 ( loop ) 를 생성 하 지 않 는 가장 짧 은 간선 이 다 . CE 의 색 을 변경 하 였 다 . 같 은 방식 으로 고르 면 다음 간선 은 DF 이 다 . 무게 ( weight ) 는 6 이 다 . 다음 으로 가장 짧 은 간선 은 AB 와 BE 인데 , 둘 다 길이 ( = 무게 ( weight ) ) 가 7 이 다 . 임의로 AB 를 골랐 다 . BD 는 빨 강색 으로 변경 하 였 는데 , ABD 를 연결 시키 면 루프 를 이루 기 때문 이 다 . 다음 으로 가장 짧 은 간선 은 BE 로서 길 이 7 이 다 . 더 많 은 간선 들 이 빨강 으로 변했 다 . BCE 루프 를 생성 하 기 때문 에 BC 가 빨 강색 으로 변했 으며 , DEBA 루프 를 생성 하 기 때문 에 DE 가 빨 강색 으로 변했 고 , FEBAD 루프 를 생성 하 기 때문 에 FE 가 빨 강색 으로 변했 다 . 끝내 , EG 가 연결 되 면서 알고리즘 이 종료 된다 . 미니멈 스 패닝 트리 가 완성 되 었 다 . 알고리즘 정확 성 의 증명 P 를 정점 들 이 연결 된 ( connected ) 무게 값 이 있 는 ( weighted ) 그래프 라고 가정 하 자 . 또한 Y 를 크루스 칼 의 알고리즘 을 써서 만들 어 낸 P 의 서브 그래프 라고 가정 하 자 . Y 는 순환 고리 ( cycle ) 을 가질 수 없 다 . 마지막 간선 ( edge ) 이 하나 추가 되 어 순환 고리 를 생성 한 것 이 라면 , 그 마지막 간선 ( edge ) 은 서로 다른 트리 사이 에 존재 할 수 없 으며 , 한 서브 트리 내 에 존재 해야 만 하 기 때문 이 다 . ( 순환 고리 를 만들 려면 각 정점 들 이 한 서브 트리 내 에서 이미 이어져 있 어야 한다 . 알고리즘 의 절차 상 그러 한 마지막 간선 ( edge ) 을 만들 수 없 다는 뜻 이 다 . ) Y 는 연결 안 된 ( disconnected ) 그래프 일 수 가 없 다 . Y 내 에 연결 안 된 콤 포 넌 트 가 있 었 다면 , 알고리즘 의 절차 에 의해 , 그 둘 을 연결 하 는 간선 ( edge ) 가 추가 되 었 을 것 이 기 때문 이 다 . 결론 을 내리 면 , Y 는 P 의 스 패닝 트리 이 다 . 다음 으로 는 스 패닝 트리 Y 가 미니멈 스 패닝 트리 임 을 보이 겠 다 . Y 1 이 미니멈 스 패닝 트리 라고 가정 하 다 . 만약 Y = Y 1 이면 Y 도 미니멈 스 패닝 트리 가 된다 . 이게 사실 이 아니 라고 가정 하 자 . e 가 Y 에 는 있 으나 Y 1 에 는 없 는 간선 ( edge ) 라고 가정 하 자 . 는 순환 고리 ( cycle ) 을 가질 수 밖 에 없 다 . 스 패닝 트리 에 간선 을 하나 더하 면 더 이상 스 패닝 트리 가 아니 기 때문 이 다 . 이 순환 고리 ( cycle ) 은 다른 하나 의 간선 ( edge ) f 를 가지 는데 , f 는 e 가 Y 에 추가 되 는 알고리즘 의 단계 에서 고려 안 된 간선 ( edge ) 일 수 밖 에 없 다 . 안 그랬 다면 e 는 같 은 트리 의 다른 브랜치 ( branch ) 들 을 서로 연결 했 을 것 이 고 , 서로 다른 트리 들 은 연결 시키 지 않 았 을 것 이 기 때문 이 다 . 그러므로 도 역시 스 패닝 트리 이 다 . 이 스 패닝 트리 의 총 무게 합 ( total weight ) 은 Y 1 의 총 무게 합 ( total weight ) 보다 작 다 . 그 까닭 은 이 므로 알고리즘 이 f 를 방문 하 기 전 에 e 를 먼저 방문 했 기 때문 일 것 이 다 . 만약 무게 값 ( weight ) 들 이 같 았 다면 , 우리 는 Y 에 는 있 으나 Y 1 에 는 없 는 간선 ( edge ) e 를 생각 할 수 있 다 . 만약 남 아 있 는 간선 ( edge ) 이 없 었 다면 , Y 나 Y 1 가 서로 다른 간선 ( edge ) 들 로 구성 되 어 있 었 더라도 Y 의 총 무게 합 이 Y 1 의 총 무게 합 과 같 을 것 이 다 . 이 때 도 역시 Y 는 미니멈 스 패닝 트리 가 된다 . 만약 Y 2 의 총 무게 합 이 Y 1 의 총 무게 합 보다 작 은 경우 에 는 , Y 1 이 미니멈 스 패닝 트리 가 아니 라는 결론 에 다 다르 게 된다 . 이것 은 w ( e ) < w ( f ) 인 간선 ( edge ) e , f 가 있 다는 처음 의 가정 에 위배 되 게 된다 . 결론 적 으로 , Y 는 ( Y 1 과 간선 들 도 같 고 , 무게 도 같 은 ) 완전 한 미니멈 스 패닝 트리 가 될 수 밖 에 없 다 .