Prim 알고리즘

Goal

• Prim 알고리즘에 대한 이해
• Prim 알고리즘을 구현할 수 있다.
• Prim 알고리즘이 사용되는 예시를 들 수 있다.

---

Prim(Prim's algorithm)

트리를 확장해 나갈 때 인접 정점 중 간선 가중치가 가장 작은 정즘을 선택하여 트리를 확장해 나가는 알고리즘

 

Prim알고리즘 동작 과정

1. 그래프에서 정점 하나를 선택해서 트리를 만든다.
2. 현재 트리가 n-1개의 간선을 가질 때 까지 다음 과정을 반복한다. (n은 그래프 전체 노드 개수)
   1. 트리에 포함되지 않은 인접 정점 중, 간선 가중치가 가장 작은 정점을 트리에 추가한다.

트리에 정점 v가 추가 되면, 트리에 인접한 정점이 갱신 될 수 있다. (v에 연결 되어 있으면서 트리에 없는 정점) 

 

또한, 트리와 인접 정점 사이의 최소 가중치가 갱신 될 수 있다.

즉, v를 통해 트리와 정점이 연결될 때 기존 연결 되어 있던 최소 가중치보다 더 적은 가중치 값을 갖는다면, 해당 값으로 갱신된다.

 

다음 그림은 Prim 알고리즘을 사용하여 최소 신장 트리를 만드는 예시이다.

 

Prim알고리즘의 성능

시간 복잡도

1. 인접행렬 : O($V^2$)
2. 이진 힙과 인접 리스트 : O((V+E)$\log_2{V}$) = O($E\log_2{V}$)
3. 피보나치 힙과 인접 리스트 : O($E+V\log_2{V}$)

인접은 성능이 안좋고,

 

Prim 알고리즘 구현

[BOJ 1922 문제]

인접 행렬로 구현한 Prim 알고리즘

#include<cstdio>
#include<algorithm>

#define MAX 1001
#define INF 10001

using namespace std;

int N, M;

bool mst[MAX] = { false, };
int weights[MAX]; // MST에 포함될 정점의 가중치(트리가 확장해 나감에 따라 인접 정점들 사이의 가중치 값이 갱신된다.)
int edge[MAX][MAX];

int getMinVertex(bool* mst, int* weights)
{
    int minVertex = 0;
    int minWeight = INF;

    for (int v = 0; v < N; v++)
    {
        // 현재 트리와 인접한 정점 중 가중치가 가장 작은 정점 선택
        if (false == mst[v] && weights[v] < minWeight)
        {
            minVertex = v;
            minWeight = weights[v];
        }
    }

    return minVertex;
}

void prim(int s)
{
    int cnt = 0; // 현재 트리에 포함된 간선 개수

    int minVertex = s;
    mst[minVertex] = true; // 시작 정점을 트리에 추가

    for (int i = 0; i < N; i++)
    {
        weights[i] = INF; // 아직 mst에 포함된 간선이 없기 때문에 weight를 모른다.
    }
    weights[s] = 0; // self-loop는 없으므로 가중치 0 (나머지 n-1개의 간선은 weight값이 존재)

    while (cnt < N - 1) // n-1개의 간선을 가질 때까지 반복
    {
        for (int v = 0; v < N; v++)
        {
            /*
            아래 구문은 추 후 MST에 포함될 정점의 weight값을 갱신하는 과정이다.
            다음 조건을 만족하는 상황에서 갱신될 수 있다.
                1. 트리에 포함되지 않은 정점이여야 한다.
                2. 트리에 인접해 있어야 한다. (현재 추가되는 정점을 통해 트리와 연결 되는지 확인)
                3. 추가되는 정점을 통해서 트리와 연결 될 때 가장 작은 가중치 값을 갖는다면 weight값은 갱신된다.
            */

            if (false == mst[v] && edge[minVertex][v] != INF) // 1,2번 조건
            {
                if (edge[minVertex][v] < weights[v]) // 3번 조건
                {
                    weights[v] = edge[minVertex][v];
                }
            }
        }

        minVertex = getMinVertex(mst, weights);
        if (weights[minVertex] == INF) // connected graph가 아닌 경우 예외 처리
        {
            return;
        }

        mst[minVertex] = true; // MST 인접 노드 중 가중치가 최소인 정점을 mst에 포함 시킨다.
        cnt++;
    }
}

int main(void)
{
    scanf("%d %d", &N, &M);

    //init
    fill(&edge[0][0], &edge[MAX][MAX], INF);

    int u, v, w;
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        edge[u-1][v-1] = edge[v-1][u-1] = w;
    }

    prim(0);

    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        sum += weights[i];
    }
    printf("%d", sum);
    
    return 0;
}

 

힙을 사용한 Prim 알고리즘

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 1001;

int V, E, totalCost;
bool visited[MAX] = { false, };

struct edge
{
    int adj, w; // 인접 정점, 가중치

    bool operator <(const edge& e) const
    {
        return (w > e.w); // <연산자로 greater 비교
    }
};

priority_queue<edge, vector<edge>> heap;
vector<vector<edge>> graph;

void prim(int s)
{
    visited[s] = true; // 최초 노드를 트리에 넣는다
    
    // 시작 노드와 인접한 간선을 heap에 넣는다.
    for (edge e : graph[s])
    {
        heap.push(e); // 트리와 인접한 노드와 연결된 간선을 heap 넣는다.
    }

    while (!heap.empty())
    {
        edge minEdge = heap.top();
        heap.pop();

        if (visited[minEdge.adj]) // 간선의 두 정점이 이미 트리에 포함 되어 있는 경우
            continue;

        int v = minEdge.adj; // 새로 추가할 노드

        // 트리에 없는 새로운 노드를 잇는 간선이 최소 비용 간선일 경우 트리에 노드를 넣는다.
        visited[v] = true;
        
        // MST에 간선이 추가되므로 cost계산
        totalCost += minEdge.w;

        // 새로운 정점이 추가 됐으므로, heap에 새로 추가할 간선 체크
        for (edge e : graph[v])
        {
            if (!visited[e.adj]) // 트리에 포함되어 있지 않은, 인접 간선만 힙에 넣는다.
            {
                heap.push(e);
            }
        }
    }
}

int main()
{
    scanf("%d %d", &V, &E);
    graph.resize(V + 1);

    int u, v, w;
    for (int i = 0; i < E; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back({ v, w });
        graph[v].push_back({ u, w });
    }

    prim(1); // 1번 정점으로 트리를 만들어 시작
    printf("%d\n", totalCost);

    return 0;
}

 

Prim 알고리즘 정리

• 정점을 기반으로 트리를 확장해 나간다.
• 시간 복잡도
  1. 인접행렬 : O($V^2$)
  2. 이진 힙과 인접 리스트 : O(ElogV)
  3. 피보나치 힙과 인접 리스트 : O(E+VlogV)
• 밀집 그래프(Dense Graph)에 적합한 알고리즘

---

References

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

https://dev-jk.tistory.com/28