prim

图论 C++ 公开

#include <bits/stdc++.h>
using namespace std;

const int N = 100;     // 假设最多有 100 个点
const int INF = 1e9;   // 用一个很大的数表示“没有边”或“距离无限大”

int n;                 // 图中点的数量
int g[N][N];           // 邻接矩阵 g[i][j] 表示 i 到 j 的边的权值
int dis[N];            // dis[i] 表示“点 i 到当前生成树的最小距离”
bool vis[N];           // vis[i] 表示“点 i 是否已经被加入生成树”



int main() {
    cout << "请输入点的数量 n：" << endl;
    cin >> n;

    cout << "请输入邻接矩阵（没有边用很大数或0表示）：" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
            if (i == j) g[i][j] = INF; // 自己到自己不算边
            if (g[i][j] == 0) g[i][j] = INF; // 若输入0表示无边，则转为INF
        }
    }

    // 初始化每个点到生成树的最短距离为无穷大
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = false;
    }

    // 调用 Prim 算法
    int result = prim();

    cout << "最小生成树的总权值为：" << result << endl;

    return 0;
}
/*
4
0 3 5 0
3 0 4 6
5 4 0 2
0 6 2 0

9

*/