고인물을 지양하는 블로그

크루스칼 알고리즘은 여러 개의 트리를 하나의 트리로 키워나가는 알고리즘이다. 간선의 길이가 짧은 엣지 순으로, 두 정점 {u,v}가 서로 다른 집합에 있으면 연결한다. 슈도 코드는 다음과 같다. MST = ∅ 모든 v ∈ G.Vertex에 대해: v가 속한 집합을 자기 자신(v)로 초기화 (u, v) ∈ G.Edge 의 가중치가 증가하는 순서대로 정렬; 정렬된 (u, v) ∈ G.Edge 에 대해 n-1개의 Edge가 추가될 때 까지: if FIND-SET(u) ≠ FIND-SET(v): // 정점 u, v가 속한 집합이 다르면 (서로 연결이 안됐으면) MST = MST ∪ {(u, v)} // MST에 엣지 추가 UNION(FIND-SET(u), FIND-SET(v)) //u, v 같은 집합에 추가 (..