Prim算法

本文主要是介绍Prim算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例如;如下图，构造一棵最小生成树

构造过程：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
using namespace std;
const int maxx=505;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];//记录两点之间的权值 
int n,m;
int vis[maxx];//记录访问情况 
int dist[maxx];//记录最短距离 
int p[maxx];//记录前驱节点 
int mincost;//记录最小费用 
void Prim(int u){
	for(int i=1;i<=n;i++){
		dist[i]=e[u][i];
		p[i]=u;
	}
	vis[u]=1;
	dist[u]=0;
	for(int i=1;i<=n;i++){
		double temp=inf;
		int t=u;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dist[j]<temp){
				temp=dist[j];
				t=j;
			}
		} 
		if(t==u)break;
		vis[t]=1;
		mincost+=dist[t];
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dist[j]>e[t][j]){
				dist[j]=e[t][j];
				p[j]=t;
			}
		}
	}
}
int main(){
	int t;
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j){
					e[i][j]=0;
				}else{
					e[i][j]=inf;
				}
			}
		}
		memset(vis,0,sizeof(vis));
		memset(p,0,sizeof(p));
		memset(dist,inf,sizeof(dist));
		for(int i=1;i<=m;i++){
			int a,b,cost;
			scanf("%d %d %d",&a,&b,&cost);
			e[a][b]=e[b][a]=cost;
		}
		mincost=0;
		Prim(1);
		cout<<"最小费用: "<<mincost<<endl;
	}
	return 0;
}
/*
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 5 6
5 6 6
3 6 4
3 4 5
4 6 2
*/

这篇关于Prim算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！