[알고리즘 기본]Kruskal 알고리즘

Kruskal 알고리즘 

MST(최소 신장 트리)를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

오늘은 크루스칼 알고리즘에 대해 더 자세히 살펴보도록 하겠다.

 

크루스칼 알고리즘은 일단 모든 간선을 오름차순으로 정렬하고

순서대로 이어나가다가 사이클이 발생하면 해당 간선은 건너뛴다. 참으로 간단하다.

 

크루스칼은 프림에 비해 희소 그래프인 경우, 그러니까 간선이 적은 경우 적합하고,

프림은 크루스칼에 비해 간선이 많이 존재하는 밀집그래프에 더 적합하다.

 

프림 알고리즘은 아래에서 더 자세하게 다룬다.

https://jinniepark.tistory.com/46

[알고리즘 기본]PRIM 알고리즘

 

일단을 개념적으로 구하는 방법을 그려보았다.

---

 

 

이때 사이클을 검사하는 알고리즘은 Union-Find 알고리즘이 쓰인다.

---

관련문제

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

https://jinniepark.tistory.com/56?category=952224

[백준][1922]네트워크 연결