[파이썬 자료구조] Kruskal 알고리즘

[파이썬 자료구조] 그래프(Graph)

최소신장트리(MST)는 edge의 가중치의 합이 최소인 신장트리임

신장트리란? 모든 정점을 연결하는 트리라고 생각하면됨. 

Kruskal 알고리즘

가중치의 크기순서대로  간선을 추가하며, 싸이클이 만들지 않는 알고리즘임

최소신장트리(MST)를 만드는 알고리즘

예제를 보면 7개의 정점과 12개의 edge가 있음. 각각의 edge에는 가중치가 있음.

0단계. edge를 가중치에 따라 정렬을 함 

1단계. 정렬순서대로 (4,6)을 연결하는 edge의 가중치가 가장 작으므로 정점4와 정점6을 연결함

2단계. (2,5)를 연결

3단계. (1,6)을 연결

4단계. (3,5)을 연결

5단계. (1,4)를 연결하면 (1,4,6)의 싸이클이 만들어지므로 (1,4)를 버림

6단계. (5,6)을 연결

7단계. (2,4)를 연결하면 싸이클이 만들어지므로 버림

8단계. (3,6)을 연결하면 싸이클이 만들어지므로 버림

9단계. (0,1)을 연결

10단계. 더 이상 연결할 수 없으므로 끝

예제에서 최소신장트리의 간선의 가중치의 합은 25

수행시간

edge를 정렬하는데 걸리는 시간은 mlogm (m: edge의 개수) + cycle여부를 확인하는데 걸리는 수행시간

다음 포스팅에서 cycle여부를 확인하는 방법을 알아보자

[파이썬 자료구조] Partition or Disjoint Set