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$ 的一棵最小生成树。

• 若 $Y=Y1$，显然 prim 算法是正确的。

• 若Y≠Y1，可进行如下推导：

1. $Y$ 中有 $n(n\geq1)$ 条边不存在于 $Y1$ 中，在构建 $Y$ 的过程中，第一次遇到这样的一条边时（以 $e$ 表示），则 $e$ 的一个端点 $u$ 落在 $V$ 内（$V$ 是之前的 prim 运算得到的一个子顶点集)，另一个端点 $v$ 落在 $V$ 外；
2. $Y1$ 是连通的，故 $Y1$ 中存在 $u$ 到 $v$ 的一条的路径，此路径上必然存在一条边 $f$，它的一个端点落在 $V$ 内，另一个端点落在 $V$ 外；
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。