用C++编辑最小生成树问题

在C++中，可以使用Prim算法或者Kruskal算法来求解最小生成树问题。下面是使用Prim算法的示例代码：

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

using namespace std;

// 定义边的结构体
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重
};

// Prim算法求解最小生成树
void prim(vector<vector<Edge>>& graph, int start) {
    int n = graph.size(); // 图的节点数

    // 创建一个优先队列，用于选择最小权重的边
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    vector<int> dist(n, INT_MAX); // 存储节点到最小生成树的距离
    vector<bool> visited(n, false); // 记录节点是否已经加入最小生成树

    dist[start] = 0; // 起始节点到自身的距离为0
    pq.push(make_pair(0, start)); // 将起始节点加入优先队列

    while (!pq.empty()) {
        int u = pq.top().second; // 获取当前权重最小的节点
        pq.pop();

        visited[u] = true; // 将节点标记为已访问

        // 遍历与当前节点相邻的边
        for (auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 如果节点v未加入最小生成树且权重小于dist[v]
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight; // 更新节点v到最小生成树的距离
                pq.push(make_pair(dist[v], v)); // 将节点v加入优先队列
            }
        }
    }

    // 输出最小生成树的边和权重
    for (int i = 1; i < n; i++) {
        cout << "Edge: " << i << " - " << dist[i] << endl;
    }
}

int main() {
    int n, m; // 节点数和边数
    cin >> n >> m;

    vector<vector<Edge>> graph(n); // 存储图的邻接表表示

    // 读取边的信息
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;

        // 添加边的信息到邻接表中
        graph[u].push_back({v, weight});
        graph[v].push_back({u, weight});
    }

    int start; // 起始节点
    cin >> start;

    prim(graph, start); // 使用Prim算法求解最小生成树

    return 0;
}

这段代码使用了邻接表来表示图，通过输入节点数、边数和边的信息，然后调用prim函数来求解最小生成树。prim函数使用了优先队列来选择权重最小的边，并使用dist数组来记录节点到最小生成树的距离。最后输出最小生成树的边和权重。