Kruskal 알고리즘

방법

한 번에 하나씩 비용이 가장 적은 간선을 선택하여

T에 이미 포함된 간선들과 사이클을 형성하지 않는 간선들만을 차례로 T에 추가

T에 n-1개의 간선들이 존재하면 멈춤

 

특징

인접 행렬, 리스트가 아닌 table 사용

E 배열

v	w	cost

T 배열

(0으로 초기화 된 T에 조건 만족하는 i번째 간선 삽입)

i

0

0

 

 

T=Ø

while ( (T가 n-1개 미만의 간선 포함) && (E != empty) ) {
   E에서 최소 비용 간선 (v, w) 선택
   E에서 (v, w) 삭제
   
   if ( (v, w)가 T에서 사이클 미형성 )
      T에 (v, w) 추가
   else
      (v,w) 거부
}

if (T가 n-1개 미만 간선 포함)
   cout << "신장 트리 없음 " << endl;