朴素版Prim算法

朴素版的Prim算法

适合稠密图 ，稠密图适合用邻接矩阵存储
核心操作
1、 dist[i] 初始化为正无穷
2、集合s 表示在当前连通块内的所有点
3、for(i=1~n)
找到在集合外的距离最近的点->t
4、用t来更新其他点到集合的距离
5、把他加入到集合当中去 st[t]=true;
  （边的正负都可以）

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dis[N];//表示集合外的点到集合的距离
bool vis[N];
int Prim() {
    memset(dis, 0x3f, sizeof(dis));//到集合的距离初始为无穷
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int t = -1; //判断是否为初始点
        for (int j = 1; j <= n; j++) {

            if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
                t = j;//如果是初始点则加入到集合 或者如果到集合的距离最小则加入到集合
            }
        }
        if (i > 1 && dis[t] == INF)return INF;//如果不是初始点 且 到集合的最小距离是无穷 则返回impossible
        if (i > 1) res += dis[t]; //如果不是初始点 则累加最小生成树边权
        vis[t] = true;//将点加入到集合中
        for (int j = 1; j <= n; j++) {//用新加入的点更新距离
            dis[j] = min(dis[j], g[t][j]);//g[t][j] 表示j到集合的距离
        }
    }
    return res;
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));  //图初始距离都为无穷
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); //由于是无向图 所有 g[a][b]和g[b][a]都初始化
        g[b][a] = min(g[a][b], c);
    }
    int t = Prim();
    if (t == INF)
        cout << "impossible" << endl;
    else cout << t << endl;
    return 0;
}