【算法】Prim最小生成树算法

目录

一、思想

二、代码

在阅读本文前推荐优先食用：

【算法】Kruskal最小生成树算法-CSDN博客https://blog.csdn.net/Eristic0618/article/details/143312482?spm=1001.2014.3001.5501

一、思想

Kruskal算法基于边的选择，因此更适用于稀疏图。而对于基于选择节点的Prim最小生成树算法，其更适用于边数量远大于节点数量的稠密图

Prim算法的思想如下：

• 选择一个起始点作为连通块的一部分，更新其他节点距离连通块的最短距离
• 每次选择离连通块距离最短的节点，将其加入连通块，并更新其他节点距离连通块的最短距离
• 重复上一步，直到所有节点都包含在连通块内，构成一颗最小生成树

例如下面这个图：

我们以1号节点作为起始节点加入连通块，其他所有节点距离连通块的距离初始化为最大值

更新其他节点距离连通块的最短距离

从所有没有被加入连通块的节点中，找出离连通块距离最短的节点（此处为V3），加入连通块

更新其他节点距离连通块的最短距离，因为V3是新加入连通块的节点，所以实际上只需要判断其他未加入节点距离V3的距离是否小于自己原来的最短距离即可

继续找距离最短节点，此处V4和V6距离连通块的距离都为4，说明最小生成树不一定是唯一的。此处我们选择V4，将其加入连通块并更新距离

V6距离连通块最近，将V6加入连通块并更新距离

V2最近，将V2加入连通块并更新距离

最后是V5

所有节点都被加入连通块后，我们就得到了图中的最小生成树

二、代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;

#define N 510
#define M 1000010

int	n, m;
int dist[N]; //节点到连通块的最短距离 
int g[N][N]; //邻接矩阵
bool st[N];  //判断某节点是否在连通块中 

int Prim()
{
	memset(dist, 0x3f, sizeof dist); //初始化dist数组 
	dist[1] = 0;
	
	int res = 0; //最小生成树边权和 
	for(int i = 0; i < n; i++) //起始节点已加入连通块，遍历剩余n-1个节点
	{
		int t = -1; //标记当前遍历中与连通块距离最小的节点编号 
		for(int j = 1; j <= n; j++) //遍历所有节点 
		{
			if(!st[j] && (t == -1 || dist[t] > dist[j])) //节点j不在连通块中 且 当前未选择节点或节点j距离比节点t更短
				t = j; //更新t 
		}
		//经过循环，此时节点t就是 剩余所有不属于连通块中的节点 中 距离连通块最短的节点 
		if(dist[t] > INF / 2) return INF; // dist[t]仍为最大值，说明剩余节点不与连通块相连
		
		res += dist[t]; //将t距离连通块的距离加入边权和 
		
		for(int j = 1; j <= n; j++)
		{
			dist[j] = min(dist[j], g[t][j]); //更新剩余节点到连通块的最短距离 
		}
		
		st[t] = true; //将节点t加入连通块 
	}
	return res;
}

void solve()
{
	cin >> n >> m;
	
	memset(g, 0x3f, sizeof g); //所有权重全部初始化为最大值 
	for(int i = 0;i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		g[a][b] = g[b][a] = min(g[a][b], w); //无向图and可能存在重边 
	}
	
	int ret = Prim();
	
	if(ret == INF) cout << "impossible" << endl;
	else cout << ret << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

完.