最小生成树（prime算法）

桃扇骨 2021-06-22 15:37 532阅读 0赞

**伪代码**
    S:当前已经在联通块中的所有点的集合
        dist[i] = inf
        for n 次
        t<-S外离S最近的点
        利用t更新S外点到S的距离
        st[t] = true
       n次迭代之后所有点都已加入到S中
    Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

#include <iostream>
    #include <cstring>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int n,m;
    int res;
    int dist[510];//dist存储其他点到st集合的距离
    bool st[510];//判断是否在集合 
    int g[510][510];//邻接矩阵存储所有边

int prime(){ 
    	memset(dist,0x3f,sizeof(dist));
    	for(int i=0;i<n;i++){ 
    		int t=-1;
    		for(int j=1;j<=n;j++){ 
    			if(!st[j]&&(t==-1||dist[t]>dist[j])){ 
    				  t=j;//找到不在st集合中，距离集合最小的那个点 
    			}
    		}
    		if(i&&dist[t]==INF){ 
    		//如果不是第一个点，距离为正无穷，说明当前最小的点都为正无穷
    		//即不连通，不存在最小生成树 
    			return INF;
    		}
    		if(i){ 
    			res+=dist[t];//如果不是第一个点就加上该点st集合的距离 
    			
    		}
    		st[t]=true;
    		for(int j=1;j<=n;j++){ 
    			 dist[j]=min(dist[j],g[t][j]);
    			 //更新到集合st最短距离
    			 //注意这里和Dijkstra算法不同，
    			 //Dijkstra是用到起始点最短的距离来更新
    			 //prime则是用到集合的最短距离来更新 
    		}
    	}
    	return res;
    }
    int main(){ 
    	memset(g,0x3f,sizeof(g));
    	cin>>n>>m;
    	while(m--){ 
    		int a,b,c;
    		cin>>a>>b>>c;
    		 g[a][b]=g[b][a]=min(g[a][b],c);//无向图，存在从边，每次取最小值 
    	}
    	int t=prime();
    	 //临时存储防止调用两次prime函数导致最后仅返回0
    		if(t==INF){ 
    		cout<<"impossible"<<endl;
    	}
    	else{ 
    		cout<<t<<endl;
    	}
    	return 0;
    }