이곳은 개발을 위한 베타 사이트 입니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.

크루스칼 알고리즘

덤프버전 :

분류

이 문서는 토막글입니다.

토막글 규정을 유의하시기 바랍니다.



1. 개요
2. 구현방법


1. 개요[편집]

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


2. 구현방법[편집]

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



[1] 정렬해도 된다.[2] 이 과정을 Union Find으로 수행할 수 있다.

관련 문서