prim算法求最小生成树（贪心）

⬅ 返回

1、思路

2、例题

3、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e3+15;
const int mod = 1e9+7;
int g[N][N];//储存点和边
int dist[N];//dist表示的是点到集合的距离
int st[N];//st判断点是否在集合中
int n,m; 
 
//与朴素的迪杰斯特拉算法类似
int prim(){
	
	dist[1]=0;
	int res=0;
	for(int i=1;i<=n;i++)//一轮找一个顶点，共需要找n轮 
	{
		int t=-1;
		for(int j=1;j<=n;j++)//找到离集合最近的点 并且不在集合中 
		{
			if(st[j]==0 && (t==-1 || dist[j]<dist[t]))
			{
				t=j;
				//cout<<dist[j]<<" j "<<j<<" "<<dist[t]<<" t "<< t <<endl;
			}
		}
		if(dist[t]==MAX_INT)//如果离集合最近的点为无穷大 那么不存在最小生成树
		    return MAX_INT;
		st[t]=1;//加入集合
		res+=dist[t];
		//更新其他边的距离 dist是到集合的距离
		for(int j=1;j<=n;j++)
		{
			dist[j]=min(dist[j],g[t][j]);
		} 
		 
	}  
	return res;
	
}
 
void solve()
{
	cin>>n>>m;
	memset(dist,0x3f,sizeof dist);//初始化点到集合的距离为无穷
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c);//无向图需要两条有向边****
	}
	auto ans = prim();
	if(ans==MAX_INT)
	    cout<<"impossible"<<endl;
	 else
	    cout<<ans<<endl;
 
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int T = 1;
    while(T--)
    {
        solve();
    }
}