最小生成树算法-Prim算法

21 Jun 2023 in Algorithm Pageviews

use prim easily!

最小生成树： 给定一张边带权的无向图 G=(V,E)，其中 V表示图中点的集合，E 表示图中边的集合，n=

V

，m=

E

。由 V 中的全部 n个顶点和 E 中 n−1条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。

普利姆(Prim)算法

题目举例：

给定一个 n个点 m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边的权重之和。

算法思路：

include<bits/stdc++.h>

constexpr int INF = 0x3f3f3f3f;
constexpr int N = 10010;
int dist[N];
int g[N][N];
int vis[N];
int n = 0;
int m = 0;

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        if ((i != 0) && (dist[t] == INF)) {
            return INF;
        }
        
        if (i != 0) {
            res += dist[t];
        }

        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], g[t][j]);
        }
        vis[t] = true;
    }
    return (res == INF) ? -1 : res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < m; i++) {
        int u = 0, v = 0, w = 0;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    int res= prim();
    return res;
}