[그래프]Prim

Prim

Kruskal과 같이 어떤 그래프로부터 최소 신장 트리(Minimum Spanning Tree)를 도출해낼 때 사용하는 알고리즘

kruskal과의 비교

Kruskal은 간선을 순차적으로 나열해서 가장 적은 비용이 드는 간선들을 선택하는 방식 (간선 중심)
Prim은 한 정점을 선택하고 그것과 연결된 가장 적은 비용의 정점을 선택하는 방식 (정점 중심)

상황에 따라 이 두 알고리즘을 적절히 사용하면 되는데, 간선이 적은 희소 그래프에선 Kruskal을 사용하고 간선이 많은 밀집 그래프에선 Prim을 사용하면 효율적이다.

시간복잡도

O(elogv)

예시 코드

#define pii pair<int, int>
#define MAX_SIZE 100000

vector<pii> adj[10001];
bool visited[MAX_SIZE];
 
int prim(int v, int e){
    int mstCost = 0;
    int selectCnt = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    pq.push({0, 1}); //(cost, start_node)
    
    while(!pq.empty()){
        int here = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        
        if(visited[here])    continue;
        visited[here] = true;
     
        mstCost += cost;
        if(++selectCnt == v)    break;
        for(int i = 0; i < adj[here].size(); i++)
        {
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            if(!visited[next]).   pq.push(make_pair(nextCost, next));
        }
    }
    if(selected == v).   return mst_cost;
    else    return -1;
}