prim 最小生成树算法

· · 算法·理论

对于最小生成树的定义解释，我在讲 kruskal 算法的文章中已经提到过了。

prim 算法

背景介绍

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为 DJP 算法、亚尔尼克算法或普里姆－亚尔尼克算法。

Prim 的思想与 dijkstra 相似，都是由已知点扩展到未知点，然后逐层扩大，以求出答案的算法。

思路

Prim 算法一开始规定 1 号点属于最小生成树，并且将 1 号点的所有边加入集合 q，选择集合 q 中最短的边，将这条边连接的点加入最小生成树，最小边加入树边，将这个点的所有边加入集合 q，然后再选择没有被选择过的最短的边继续操作，直到所有点都被加入最小生成树为止。

再维护集合中最小的边时，我们可以用堆或者 stl 中的 priority_queue 进行优化，堆优化后的 prim 时间复杂度是 O(m\log n)。

正确性证明

已知条件：

图 g 是一个连通图，Y 是对 g 使用 prim 算法得到的一棵生成树，Y1 是 g 的一棵最小生成树。

  3. 把 e 加入 Y1，去掉 f，Y1 仍然连通，根据 prim 算法，权值 W(f)≥W(e)，否则 e 不会被选入 V，如果 W(f)>W(e),新构建的树的权值和会比 Y1 小，而 Y1 是最小生成树，因此 W(f)>W(e) 不成立，得 W(f)=W(e)。
  4. 对每一条类似 e 的边，重复过程 c），最终 Y 和重新构建的 Y1 拥有的边完全一致，新构建的 Y1 也是最小生成树，因此 Y 也是最小生成树。

所以，证明prim算法正确。

适用范围

因为 Prim 算法时间复杂度为 m\log n，相比于时间复杂度为 m \log m 的 kruskal 算法，在稠密图中会效果更好，但由于 \log_2 m 和 \log_2 n 的差距非常小，可以忽略。

但是在极端条件和极端数据下，稠密图中，一般选择 Prim 算法，但在 n,m\leq 5\times 10^5 的数据中，通常两种算法都可过。

代码

// prim 最小生成树算法
#include <bits/stdc++.h>

using namespace std;

const int N=5003,M=2e5+3;

vector<pair<int,int>> g[N];
int n,m;
int res,ct;
int done[N];
priority_queue<pair<int,int>> pq;

void read() {
    cin>>n>>m;
  for(int i=1,st,ed,wt;i<=m;++i) {
        cin>>st>>ed>>wt;
        g[st].push_back({ed,wt});
        g[ed].push_back({st,wt});
    }
}

void prim() {
    ct++,done[1]=1;
    for(auto c:g[1]) 
        if(!done[c.first])
            pq.push(make_pair(-c.second,c.first));

    while(pq.size()) {
        auto tp=pq.top();
        pq.pop();
        int st=tp.second,wt=-tp.first;
        if(done[st]) continue;
        res+=wt;
        ct++;
        done[st]=1;
        for(auto c:g[st])
            if(!done[c.first])
                pq.push(make_pair(-c.second,c.first));
    }

    if(ct!=n) cout<<"orz\n";
    else cout<<res<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    read();
    prim();

    return 0;
}

模板题：https://www.luogu.com.cn/problem/P3366。