Krusdal's algorithm(크루스칼)

크루스칼 알고리즘은 비방향성 가중치가 있는 그래프에서 최소비용 신장트리를 구하기 위한 알고리즘이다.

위 그림과 같은 그래프가 있다고 가정 할 때, 

각 이음선의 가중치를 오름차순으로 정렬하면 다음과 같다.

(v1, v2) 1

(v3, v5) 2

(v1, v3) 3

(v2, v3) 3

(v3, v4) 4

(v4, v5) 5

(v2, v4) 6

이젠 이음선을 차례로 선택하기만 하면 된다. 

단, 조건이 하나 있는대 선택한 이음선에 연결된 각 정점이 적어도 하나는 선택되지 않은 파란색 정점이어야 한다.

이 조건을 만족시키며 선택하면 다음 그림과 같이 전개도를 확인가능하다.

(v1, v2) 선택

(v3, v5) 선택

(v1, v3) 선택

(v2, v4) 선택

크루스칼 알고리즘도 항상 최소비용 신장트리를 보장한다.