💿 자료구조 - Kruskal Algorithm 크루스칼 알고리즘

Kruskal Algorithm

Step1) 그래프에 존재하는 모든 간선들을 가중치 순으로 나열

Step2) 그래프 내 정점이 모두 이어질 때까지 가중치가 낮은 간선 순으로 선택

- 얘 또한 cycle 형성되면 버림

- n-1개의 간선이 선택되면 알고리즘 종료

 

---

 

Kruskal Algorithm의 구현

- 가중치 '순서'로 나열 -> sort 함수 이용

 

- cycle 형성 여부 판단법

⬇️

집합으로 표현

 

 

- 같은집합을 이루는 것 표현방법

 

---

https://github.com/codenameVien/DataStructure/blob/main/KruskalAlgorithm.ipynb

DataStructure/KruskalAlgorithm.ipynb at main · codenameVien/DataStructure