프림 일고리즘

1. 개요
프림 알고리즘도 크루스칼 알고리즘의 경우처럼 한번에 하나의 간선으로 최소 비용 신장 트리를 구축한다. 그러나 알고리즘의 각 단계에서 선택된 간선의 집합은 트리를 이룬다. 

프림 알고리즘은 하나의 정점으로 된 트리 T에서 시작한다. 이 정점은 원래 그래프에서 어떤 것을 택해도 상관없다. 다음으로, 최소 비용 간선 (u,v)를 구해 T와 (u,v) 의 합집합이 트리가 되면 T에 추가한다. T 에 n-1 개의 간선이 포함될떄까지 간선의 추가 단계를 반복한다.

2. 설명











3. 알고리즘

// G 가 최소한 하나의 정점을 가진다고 가정

TV = {A}; // 정점  A로부터 시작. 간선은 비어 있음
for( T = 0; T의 간선 수가 n-1 보다 적음 ; (u,v) 를 T에 추가)
{

Let (u,v) be a least-cost edge such that u ∈ TV and v !∈ TV;
if( 그런 간선이 없음 ) break;

v를 TV에 추가; 

} 

if( T의 간선수가 n-1 보다 적음) "신장 트리가 없음" 

http://nextcube.tistory.com/m/post/194