prim 알고리즘

F=공집합;
Y={v1};
while(사례 미해결){
    Y에서 가장 가까운 V-Y에 속한 이음선을 선택;
    그 마디를 Y에 추가;
    그 이음선을 F에 추가;
    if(Y==V)
        사례해결;
}
 

nearest[i] = vi에 가장 가까운 Y에 속한 마디의 인덱스

distance[i] = vi와 nearest[i]가 인덱스인 두 마디를 연결하는 이음선의 가중치

시작할 때 Y={v1}이므로, nearest[i]는 1로 초기화하고 distance[i]는 v1과 vi를 연결하는 이음선의 가중치로 초기화한다.

프림 알고리즘

문제: 최소비용 신장트리를 구하시오.

입력: 정수 n>=2인 마디의 개수가 n인 연결된 가중치포함 비방향그래프. 그래프는 행과 열 모두 인덱스의 범위가 1부터 n까지인 2차원 배열 W로 표현한다. 여기서 W[i][j]는 i째 마디와 j째 마디를 연결하는 이음선의 가중치이다.

출력: 그래프에 대한 최소비용 신장트리 안에 있는 이음선의 집합 F

void prim(int n, const number W[][], set_of_edge& F)
{
    index i,unear;
    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++){
            if(0<=distance[i]<min){
                min=distance[i];
                unear=i;
            }
        e=unear가 인덱스인 마디를 Y에 추가한다.
        add e to F
        distance[unear]=-1;
        for(i=2;i<=n;i++)
            if(W[i][unear]<distance[i]){
                distance[i]=W[i][unear];
                nearest[i]=unear;
            }
    }
}    
 

프림 알고리즘의 일정 시간복잡도 분석

단위연산: repeat-루프 안에 있는 두 개의 for-루프가 있는데, 각각 n-1회 반복한다.

그 안에 명령문들의 한 번 실행을 단위 연산으로 한다.

입력크기: n(마디의 개수)

repeat-루프를 n-1번 반복하므로 시간복잡도는 다음과 같다.

T(n)=2(n-1)(n-1) 

이는 n^2의 차수이다.