---
tags: 演算法
title: Prim`s 演算法
---
## Prim`s 演算法
### 解決 最小生成樹(MST) 問題
> 在 **"稠密圖"** 時表現較佳

### 核心思想
> 貪心思想
> -> 選定任意一個起點開始拓展
> -> 每次都選距離現在這棵樹最短的那條邊
> -> 做完後 連起來的就會是 最小花費

> 跟 Dijkstra 很像 幾乎一樣
>
> Dijkstra -> **從找到最小花費那個點出發** 找距離最近的點 拓展
> Prim`s -> **從當前的生成樹出發** 找距離 **樹** 最近的點 拓展

### 優化
> 和 dijkstra 一樣 時間複雜度主要來自 **"提取最小值"**
> 因此一樣可以使用 priority_queue 做優化

### 實作技巧
> 一般版:
> 用 set 存已訪問過的點比較方便 -> 因為每次都要走訪集合裡所有的點

set<int> cs;
int e_count = 0 ,cost = 0;   //加入邊數和總花費
cs.insert(1);

while(e_count != V-1 ){
    int min_cost = inf, min_point = -1;
    for(int i:cs)
        for(auto j:gp[i])
            if(!cs.count(j.first)&&j.second<min_cost){
                min_cost = j.second;
                min_point = j.first;
            }
    if(min_point != -1){
        cost += min_cost;
        cs.insert(min_point);
        e_count++;
    }
}

> priority_queue 版:

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> prim;
vector<bool> cs(V+1,false);
int e_count = 0, cost=0;
prim.push({0,1});

while (e_count != V ) {   //第一次沒有加上邊只是初始化 所以是到 V
    auto t = prim.top();
    prim.pop();
    if (cs[t.second])
        continue;
    cost += t.first;
    cs[t.second] = true;
    for (auto j : gp[t.second])
        if(!cs[j.first])
            prim.push({j.second,j.first});
    e_count++;
}

#### 坑
- 請記得這會是一個 "無向圖" 所以插入邊的時候兩個點都要插 謝謝 !

### 相關題目
UVa 908:

#include "bits/stdc++.h"
#define ll long long 
#define inf 0x3f3f3f3f
using namespace std;

int main(){

    int V;
    bool f = 1;
    while(cin>>V){
        //init and input
        if (!f)
            cout << endl;
        f = false;
        vector<vector<pair<int, int>>> gp(V+1);
        int oldcost = 0;
        for(int i=1;i<V;i++){
            int s,e,w; cin>>s>>e>>w;
            oldcost += w;
        }
        int add; cin >> add;
        while(add--){
            int s, e, w;
            cin >> s>>e>> w;
            gp[s].push_back({e,w});
            gp[e].push_back({s, w});
        }
        cin >> add;
        while (add--) {
            int s, e, w;
            cin >> s>>e>> w;
            gp[s].push_back({e,w});
            gp[e].push_back({s, w});  
        }
        //prim`s algorithm
        set<int> cs;
        int e_count = 0 ,cost = 0;
        cs.insert(1);
        
        while(e_count != V-1){
            int min_cost = inf, min_point = -1;
            for(int i:cs)
                for(auto j:gp[i])
                    if(!cs.count(j.first)&&j.second<min_cost){
                        min_cost = j.second;
                        min_point = j.first;
                    }
            if(min_point != -1){
                cost += min_cost;
                cs.insert(min_point);
                e_count++;
            }
        }
        //output
        cout<<oldcost<<endl<<cost<<endl;
       
    }
    return 0;
}