C++prim算法最小生成树输出边及权值

C++ Prim算法可以用于求解带权连通无向图的最小生成树。下面是一个示例代码，用于输出最小生成树的边及权值：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 定义图的最大顶点数
const int MAX_V = 100;

// 邻接矩阵存储图
int graph[MAX_V][MAX_V];

// Prim算法求解最小生成树
void primMST(int n) {
    // 存储最小生成树的边及权值
    vector<pair<int, int>> mst;
    vector<int> key(n, INT_MAX); // 存储顶点到最小生成树的最小权值
    vector<bool> visited(n, false); // 记录顶点是否已经加入最小生成树

    // 从第一个顶点开始构建最小生成树
    key[0] = 0;

    for (int i = 0; i < n - 1; i++) {
        // 找到当前不在最小生成树中的顶点中，到最小生成树的权值最小的顶点
        int minKey = INT_MAX, minIndex;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && key[j] < minKey) {
                minKey = key[j];
                minIndex = j;
            }
        }

        // 将该顶点加入最小生成树
        visited[minIndex] = true;

        // 将该顶点与最小生成树中的顶点连接的边加入最小生成树
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIndex][j] != 0 && graph[minIndex][j] < key[j]) {
                key[j] = graph[minIndex][j];
                mst.push_back(make_pair(minIndex, j));
            }
        }
    }

    // 输出最小生成树的边及权值之和
    int sum = 0;
    for (auto edge : mst) {
        cout << edge.first + 1 << " " << edge.second + 1 << " " << graph[edge.first][edge.second] << endl;
        sum += graph[edge.first][edge.second];
    }
    cout << "权值之和：" << sum << endl;
}

int main() {
    int n, count;
    cin >> n >> count;

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    // 读入三元组
    for (int i = 0; i < count; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u - 1][v - 1] = w;
        graph[v - 1][u - 1] = w;
    }

    // 调用Prim算法求解最小生成树
    primMST(n);

    return 0;
}