[Algorithm] Prim's Algorithm

개요

Kruskal's Algorithm 과 같이 최소신장 트리를 구하는 또다른 방법.
Dijkstra's Algorithm 이랑 코드 흐름이 유사한 부분이 있다.
집합 Y에서 집합 V-Y를 연결하는 가장 낮은비용의 edge를 포함시켜나가는 방법이다.

High-level Algorithm

F = {};      // 최소신장 트리
Y = {v1}; // 집합 Y. 처음에는 v1만 포함되어있다.

While (the instance is not solved)
{
    select a vertex in V-Y that is nearest to Y;

    add the vertex to Y;
    add the edge to F;

    if (Y==V)
        the instance is solved;
}

Prim's Algorithm

W[i][j] : 초기 edge cost가 기록된 adjcant matrix
- vi에서 vj로의 이음선이 있다면 : 이음선의 가중치
- vi에서 vj로의 이음선이 없다면 : INFINITY
- i == j 라면 : 0
nearest[i] : Y에 속한 정점 중에서 vi에서 가장 가까운 정점의 인덱스 (트리를 거슬러 올라가는 parent이기도 함)
distance[i] : vi와 nearest[i]를 잇는 이음선의 가중치

// n : vertex의 개수
// W[i][j] : edge cost
// F : 반환용 최소신장트리
void prim(int n, const number W[][], set_of_edges& F)
{
    index i;               // 루프용 index
    index vnear;           // vnear : 현재 선택된 가장 가까운 V-Y vertex
    number min;            // 최소비용 vertex를 구하기 위한 거리비교변수
    edge e;                // edge 임시변수
    index nearest[2..n];   // Y에 속한 정점 중에서 vi에서 가장 가까운 정점의 인덱스
    number distance[2..n]; // vi와 nearest[i]를 잇는 이음선의 가중치

    F = {};                // 최소신장트리
    for (i = 2; i <= n; i++) // 초기화
    {
        nearest[i] = 1;         // vi들의 가장 가까운 Y점은 v1이다.
        distance[i] = W[1][i];  // vi들의 nearest[i]와 거리를 실제 거리로 초기설정.
    }

    repeat(n-1 times)
    {
        min = INFINITE;
        for (i = 2; i <= n; i++) // vnear 찾기
        {
            if (0 <= distance[i] <= min) // 방문한곳(-1)을 제외하고 가장 가까운 지점을 찾는다.
            {
                min = distance[i];
                vnear = i;
            }
        }

        e = edge connecting vertices indexed by vnear and nearest[vnear];
        add e to F;
        distance[vnear] = -1; // vnear는 Y에 편입되었다.

        for (i = 2; i <= n; i++) // 선택된 vnear에 대해서 연결된 vertex의 nearest와 distance 갱신
        {
            if (W[vnear][i] < distance[i])
            {
                distance[i] = W[vnear][i];
                nearest[i] = vnear;
            }
        }
    }
}

Complexity

Time-complexity : $O((n-1) * 2(n-1)) = O(n^2)$
우선순위큐를 사용하면 $O(mlogn)$으로 줄일수 있다. (힙을 구성하는 시간복잡도)