크러스컬 알고리즘

1 무엇인가?

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

2 어떻게 구현하는가?

• 그래프의 모든 간선의 집합 $$E$$ 을 만든다.

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