프림 알고리즘 Prim's Algorithm 일정 시간 복잡도

MST(minimum spanning tree)구하는 알고리즘

정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다.

트리가 N-1개의 간선을 가질 때까지 반복한다. 

 

의사 코드를 보면 다음과 같다.

void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선
{
	index i, vnear;
    number min;
    edge e;
    index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보
    number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단)
    
    F = ∅;
    for(i = 2; i <= n; i++) //임의로 첫 번째 정점으로 스패닝트리 시작. 초기화.
    {
    	nearest[i] = 1; 
        distance[i] = W[1][i];
    }
    
    repeat(n-1 times)
    {
    	min = ∞;
        for(i = 2; i <= n; i++) //n-1번 동안 최단 간선 찾기
        	if(0 <= distance[i] < min) 
            {
            	min = distance[i];
                vnear = i;
             }
        e = edge connecting vertices indexed by vnear and nearest[vnear];
        add e to F;
        distance[vnear] = -1;
        for( i = 2; i <= n; i++) //n-1번 동안 간선 값 업데이트하기
        	if(W[i][vnear] < distance[i])
            {
            	distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
    }
}    
        	
          
                

일정 시간 복잡도 T(n) = 2(n-1)(n-1) 인데 

N-1개의 간선을 가질 때까지 반복하는 전체적인 반복 (n-1)과 

 

그 n-1번 반복 내부에서 

인접 간선 최소값 찾는 반복 n-1번 (인접하지 않은 정점도 다 검사함. 이 때 인접하지 않은 정점의 값은 매우 큰값(무한대) )

최소 값의 간선을 찾았으면 그 새로 방문한 노드를 통해 인접 간선들의 정보를 업데이트 시켜주는 것 n-1번

(예를 들어서 1번 노드가 2번이랑만 연결되어있었는데 2번을 방문하고서는 2번에 연결된 다른 인접노드들 가중치 값이 매우 큰 값(1번 노드랑 연결 안되어 있어서 이런 값을 가지고 있었음)에서 2번 정점과 연결된 가중치 값으로 업데이트 되는 과정)

이기 때문에 (n-1)(n-1 + n-1) = 2(n-1)(n-1)인 것이다.