Prim算法和Dijkstra算法很像 复杂度是O(V^2)。用于解决稠密图的最小生成树问题。虽然可以优化到ElongE,但是这个时候还不如用kruskal算法来的简单
每次往生成树集合中加入离生成树距离最近的点,从一个点慢慢的扩展,最后得到所求的最小生成树。
#include <iostream>
#include <vector>
#define maxn 1005
using namespace std;
typedef long long ll
ll vis[maxn],cost[maxn];
//vis[i]表示i已经被用来扩展过了,cost[i]表示扩展出这个点的代价
ll g[maxn][maxn]; //完全图时用prim,可以用二维数组表示图
int main()
{
int n,m,ans = 0;
cin >> n >> m;
for( int i = 1 ; i <= n ; i++ )
{
cost[i] = 1e8;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
g[i][j] = 1e18;
}
for( int i = 0 ; i < m ; i++ )
{
ll x,y,v;
cin >> x >> y >> v;
g[x][y] = g[y][x] = v;
}
int begin; //从begin这个点来开始生成最小生成树
cost[1] = 0;
for(int i = 0; i < n; i++ ) //遍历n次生成最小生成树
{
ll minx = 1e18;
for (int j = 1; j <= n; j++) //找最小花费时直接遍历这个cost数组,寻找下一个新的节点
{
if( !vis[j] && minx > cost[j] ) //找寻新的点
{
minx = cost[j];
begin = j;
}
}
ans += minx; //代价加上花费
vis[begin] = 1; //vis置1表示该点已经使用过来更新相邻节点
for (int j = 1; j <= n; j++) //遍历该点相邻的所有边更新权值
{
if( !vis[j] && cost[j] > g[begin][j] )
cost[j] = g[begin][j];
}
}
cout << ans << endl;
return 0;
}