크러스컬 알고리즘

1. 개요

---

최소 비용 신장 트리를 $$O(ElogV)$$만에 구하는 알고리즘이다.

2. 구현방법

---

• 그래프의 모든 간선의 집합 $$E$$을 만든다.
• $$E$$가 비어있지 않을 때까지
  • $$E$$의 간선들 중 가중치가 최소인 간선을 지운다.[1]
  • 삭제된 간선이 가리키는 정점$$x, y$$를 연결하여도 사이클이 발생하지 않는다면[2] 연결한다.

[1] 정렬해도 된다.

[2] 이 과정을 Union Find으로 수행할 수 있다.