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

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.

 

즉, 크루스칼 알고리즘은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다.

 

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

그림과 같은 그래프에서 정점은 7개, 간선은 11개 이다.

 

가장 적은 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 6개 이다.

 

즉, 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 노드 개수 -1 이다.

 

최소 비용 신장 트리는 거리를 기준으로 오름차순 정렬을 한 후 그래프를 연결함으로써 만들 수 있다.

 

주의할 점은 정렬된 순서에 맞게 그래프에 포함시키기 전에 사이클이 형성되면 안된다.

 

그렇기 때문에 사이클 테이블을 먼저 확인한 후, 만약 사이클을 형성하는 경우에는 간선을 포함하지 않도록 한다.

 

최소 비용 신장 트리 도출

위 그림과 같은 과정으로 최소 비용 신장 트리를 도출해보았다. 그림에 대해 구체적으로 설명하자면,

 

(1) 거리 즉, 비용이 가장 작은 순으로 노드를 연결하기 위해 첫번째로 1과 7을 연결한다.

 

(2) 그 다음으로 적은 비용은 13이기 때문에 4와 7을 연결한다.

 

(3) 그 다음으로 적은 비용은 17이기 때문에 1과 5를 연결한다.

 

(4) 그 다음으로 적은 비용은 20이기 때문에 5와 3을 연결한다.

 

(5) 그 다음으로 적은 비용은 24이기 때문에 4와 2를 연결한다.

 

(6) 그 다음으로 적은 비용은 28인데 4와 1을 연결하면 7과 함께 사이클이 형성되기 때문에 포함시키지 않는다.

 

(7) 그 다음으로 적은 비용은 37이기 때문에 6과 3을 연결한다.

 

  ==> 최종적으로 모든 노드가 연결된 최소 비용 신장 트리가 도출된 것을 확인하고, 

          전체 노드를 연결하는 비용은 12 + 13 + 17 + 20 + 24 + 37 = 123 임을 알 수 있다.

 

---

출처

https://m.blog.naver.com/ndb796/221230994142

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