Prim 알고리즘

방법

초기 T의 정점 집합은 하나의 정점만을 포함

트리 T에 인접한 간선들 중 T와 사이클을 형성하지 않는 최소 비용 간선 (u, v)를 T에 추가

T에 n-1개의 간선이 포함될때까지 추가 단계 반복

 

// G가 최소한 하나의 정점을 가진다고 가정
TV = {0};	// 정점 0으로 시작. 간선은 empty
		// T에 포함되어 있는 양 끝점들을 포함하고 있는 집합

for (T=Ø; T 간선수 < n-1; (u, v)를 T에 추가){
   (u, v) = (u ∈ TV) && (v ∉ TV)인 최소 비용 간선
   
   if (그런 간선 없음)
      break;
      
   v를 TV에 추가
}

if (T 간선수 < n-1)
   cout << "신장트리 없음" << endl;