Prim算法 最小值生成树

前言：

给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树， 那么这棵树就叫做生成树( Spanning Tree )。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树( MST，Minimum Spanning Tree )。

例如我们假设有这样一个图:把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目-1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费,那么求解使得道路建设费用最小的生成树就是最小生成树问题。

常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。

正文：

最小生成树问题(Prim算法)

分析：

首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似,都是从某个顶点出发,不断添加边的算法。

首先，我们假设有一-棵只包含一个顶点v的树T。 然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。 接下来我们来证明通过这个方法得到的生成树就是最小生成树。

我们令V表示顶点的集合。假设现在已经求得的生成树的顶点的集合是X(属于V),并且存在在V上的最小生成树使得T是它的一个子图。下

面我们证明存在一棵最小生成树使得 T是它的一个子图并且它包含了连接X和V \X之间的边中权值最小的边。记连接x和V \X的权值最小

的边为e，它连接着V(∈X)和u(∈V\X)。根据假设，存在一棵 V上的最小生成树使得T是它的一个子图。如果e也在这棵最小生成树上,问题

就得到证明了，所以我们假设e不在这棵树上。因为生成树本质是一棵树, 所以在添加了e之后就产生了圈。

圈上的边中，必然存在一条和e不同的边f连接着x和V\X。从e的定义可以知道f的权值不会比e小。因此，我们把f从树中删除，然后加上e

就可以得到一棵新的生成树，并且总权值不超过原来的生成树。因此可以说存在同时包含e和T的最小生成树。所以把e加入T中满足最初的

假设。可以这样不断地加入新的边，直到X=V。因为存在V上的最小生成树使得T是它的一个子图，而X=V,所以T就是V上的最小生成树。

让我们看一下如何查找最小权值的边。把X和顶点V连接的边的最小权值记为dp[v]。在向X里添加顶点u时，只需要查看和i相连的边就可以了。对于每条边，更新dp[v]=min(dp[v],边(i,v)的权值)即可。

如果每次都遍历未包含在X中的点的dp[v],需要O(V^2)时间。不过和Dijkstra算法一样，如果使用堆来维护dp时间复杂度就O(E*logV)。

下面就是prim的Pro版本：

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;//n个顶点m条边
const int INF=1e9;
typedef pair<int,int> p;//first为dp值，second为顶点号 
vector<vector<int>>mp(1003,vector<int>(1003,INF));
vector<int>dp(1003,INF);
vector<int>used(1003,0);
int Prime_Pro() {
	dp[0]=0;
	int res=0;
	priority_queue<p,vector<p>,greater<p>> q;
	q.push(p(0,s));
	while(!q.empty()) {
		p temp=q.top();
		q.pop();
		int v=temp.second;
		if(dp[v]<temp.first)//如果其最新dp值与过去的某一个更新时保存的dp值大小不一时放弃选择，因为过去的dp值已无效。
			continue;
		used[v]=1;
		res+=dp[v];
		for(int i=0; i<n; ++i)
			if(!used[i]) {
				int t=dp[i];
				dp[i]=min(dp[i],mp[v][i]);//更新因该点而改变未使用的点的最小dp值 
				if(t!=dp[i])//当且仅当dp[i]已更新时才加入优先队列中 
					q.push(p(dp[i],i));
			}
	}
	return res;
}
int main() {
	cin>>n>>m;
	for(int i=0; i<m; ++i) {
		int a,b,c;
		cin>>a>>b>>c;
		mp[a][b]=c;
		mp[b][a]=c;
	}
	cout<<Prime_Pro();
}