最小代价生成树C++

最小代价生成树（Minimum Spanning Tree，MST）是一种图论算法，用于在一个加权无向图中找到一棵树，该树连接了所有顶点并且总权重（边的权值之和）最小。在C++中，最常用的算法之一是Prim算法和Kruskal算法。

**Prim算法**：
Prim算法是从图的一个选定的起点开始，每次选择一条与当前生成树中其他顶点相连、并且权重最低的新边，直到所有的顶点都被包含在树内。这个过程可以用优先队列（如`std::priority_queue`）辅助，因为我们需要频繁地查找当前最小权重的边。

**Kruskal算法**：
Kruskal算法则是按边的权重从小到大排序，然后依次加入到树中，只要这条边不会形成环就行。它通常用并查集数据结构来维护各个顶点所属的集合，当尝试添加新边时检查是否会形成新的连通分量。

在C++中，你可以使用`std::vector`、`std::set`等容器以及相应的算法来实现这两个算法。这里是一些基本步骤的概述：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// 边的数据结构，包含起始点、结束点和权重
struct Edge {
    int src, dest, weight;
};

// Prim算法实现
vector<Edge> prim(vector<Edge>& edges, int n) {
    // 使用优先队列存储未添加到树的边
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    vector<bool> visited(n);
    vector<Edge> mst;
    visited[0] = true;  // 选择第一个节点作为起点

    for (Edge edge : edges) {
        if (!visited[edge.src]) {
            pq.push({edge.weight, {edge.src, edge.dest}});
        }
    }

    while (!pq.empty()) {
        auto [weight, {src, dest}] = pq.top();
        pq.pop();

        // 检查这条边是否已经存在于树中
        if (!visited[dest]) {
            mst.push_back(edge);
            visited[dest] = true;
            // 更新未访问节点的邻接边
            for (Edge e : edges) {
                if (e.dest == dest && !visited[e.src])
                    pq.push({e.weight, {e.src, e.dest}});
            }
        }
    }
    return mst;
}

// Kruskal算法实现略...

int main() {
    // 创建图的边实例...
    vector<Edge> edges;
    // 调用上述函数获取最小代价生成树
    vector<Edge> mst = prim(edges, num_vertices);  // num_vertices表示顶点数
    // 打印最小代价生成树的边
    // ...
    return 0;
}