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

💡크루스칼 알고리즘이란?

Greedy 알고리즘으로 MST(Minimum Spannig Tree, 최소 신장 트리) 문제 해결할 때 사용하는 알고리즘. 변의 개수를 E, 꼭짓점의 개수를V라고 하면 이 알고리즘은(Elog V)의 시간복잡도를 가진다.

즉, 모든 노드를 최소한의 비용으로 연결만 시키면 되기 때문에 간선의 비용을 오름차순으로 정렬 후 비용이 작은 간선부터 차례로 노드를 연결한다.

 

📌최소 신장 트리 구성 과정

1. 간선의 비용을 기준으로 정렬

2. 정렬된 순서에 맞게 최소 비용 순으로 그래프 연결

3. 연결 전 사이클이 발생하는지 확인

4. 사이클이 발생하는 경우 그래프에 포함하지 않음.

5. 위 과정을 반복

 

• 스패닝 트리 : 1) 모든 노드(정점)을 포함하고, 2) 노드간 연결되어 있으며 사이클을 발생하지 않는 그래프
• 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리

참고자료 : https://g.co/kgs/rur57B

---

💻관련문제

섬 연결하기 : programmers.co.kr/learn/courses/30/lessons/42861