[펌]Kruskal's algorithm

1. 개요
크루스칼 알고리즘은 한번에 하나씩 최종간선그룹 T에 간선을 추가해 가면서 최소 비용 신장 트리 T를 구축한다. T에 포함될 간선을 비용의 크기 순으로 선택하며, 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가한다. 

전체 n 개의 정점을 가지고 있고 시작정점 S 에서 도착정점 G 까지 연결간선이 있다고 가정한다면 쿠르스칼 알고리즘은 정확히 n-1 개의 간선만이 T에 포함된다.

2. 설명

 

3. 알고리즘
 

T = 0; (최종 간선 집합)
while(( T 가 n-1 개 미만의 간선을 포함) && ( E(간선의 정렬된 순차 집합)는 공백이 아님)) {

E에서 최소 비용간선 (v,w) 선택

E에서 (v,w) 삭제
if(v,w) 가 T 에서 사이클을 만들지 않으면 T에 (v,w)를 추가;
else discard(v,w); 

} 

if( T 가 n-1 개 미만의 간선을 포함) "연결된 트리가 아님"; 

 

출처 : http://blog.nextcube.pe.kr/193