[이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란?

[이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란?

 

크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 그래프 G의 변들 중 비용이 가장 낮은 변들을 가지로 연결시켜 트리를 만드는 알고리즘입니다. 프림 알고리즘은 이미 연결되 노드에 근접하는 가지 중 최소 비용을 갖는 가지를 선택했지만, 크루스칼 알고리즘은 연결 여부와 상관없이 가장 비용이 낮은 가지를 연결해갑니다. 

 

▶프림 알고리즘에 대해 더 알고 싶다면

 

■ 크루스칼 알고리즘(Kruskal Algorithm) 

그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘

(1) 가중치가 가장 작은 변을 차례로 선택하여 노드들을 연결

(2) 가중치가 같은 변은 임의로 선택

(4) 선택된 변에 대해 회로가 형성되는 경우는 선택하지 않음

(5) n개의 꼭짓점에 대하여 n - 1개의 변이 연결되면 종료

 

※ 회로(Circuit): 경로의 시작점과 끝이 같은 경우

■ 크루스칼 알고리즘(Kruskal Algorithm) 예

이전 글에서 프림 알고리즘으로 만들었던 최소신장 트리를 크루스칼 알고리즘으로 만들겠습니다. 

 

 

(1) 모든 노드에 연결된 가지의 비용을 정리하면 다음 표와 같습니다. 

 

(2) (1)의 표에서 비용이 가장 낮은 노드의 연결은 A - F입니다. 

 

(3) (1)의 표에서 두 번째로 비용이 낮은 노드의 연결은 A - C와 K - G입니다. 

 

(4) (1)의 표에서 세 번째로 비용이 낮은 노드의 연결은 B - F와  F - C입니다. 그러나 F- C는 A - F - C 사이에 회로가 생성되므로 사용하지 않습니다. 

 

(5) (1)의 표에서 네 번째로 비용이 낮은 노드의 연결은 B - K입니다. 

 

(6) 모든 노드(6개)가 5(6-1)개의 가지로 연결되었으므로 종료합니다. 이때 이 최소신장 트리의 비용은 다음과 같습니다. 

9 + 10 + 12 +13 + 10 = 54 

 

각 가지에 부여된 비용이 모두 다른 경우에는 프림 알고리즘과 크루스칼 알고리즘, 두 알고리즘으로 구한 최소신장 트리의 모양이 같지만, 비용이 같은 가지를 포함한 그래프에서는 두 알고리즘으로 구한 최소신장 트리의 모양이 같을 수도 있고 다를 수도 있습니다. 

 

 

수학으로 이해하는 디지털 논리 이산수학 400p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------