贪心算法求最小生成树c++

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，希望这样的局部最优解能够累积成全局最优解。对于求解最小生成树的问题，比如著名的Kruskal's 算法（克鲁斯卡尔算法）和Prim's 算法（普里姆算法），它们都是基于贪心策略。

**Kruskal's 算法**：
1. 将所有边按照权值从小到大排序。
2. 初始化一个空集合作为最小生成树。
3. 遍历排序后的边，如果新加入这条边不会形成环，则将其添加到最小生成树中。
4. 重复步骤3，直到包含n-1条边（n为顶点数）。

**Prim's 算法**：
1. 从任意一个顶点开始，将它看作是初始树的一部分。
2. 检查未被选中的顶点中与已选中顶点连接的最短边，并将这条边及其端点加入树中。
3. 更新未选中顶点集合，并重复步骤2，直到所有顶点都被包含在树内。

**C++ 实现**：
你需要准备一个数据结构来存储图，如邻接表或邻接矩阵，然后实现两个函数分别对应这两种算法。例如，你可以创建一个`Edge`结构体来表示边，然后在循环中判断边是否符合条件。下面是一个简单的`Kruskal`函数示例：

#include <vector>
#include <set>

// 边的数据结构
struct Edge {
    int src, dest, weight;
};

bool compareEdges(const Edge& e1, const Edge& e2) { return e1.weight < e2.weight; }

std::vector<Edge> kruskal(std::vector<Edge>& edges, int n) {
    std::sort(edges.begin(), edges.end(), compareEdges);
    std::vector<Edge> mst;
    std::set<int> used Vertices;
    
    for (int i = 0; i < n - 1 && !used.size() == n; ++i) {
        int u = edges[i].src, v = edges[i].dest;
        if (used.find(u) == used.end() && used.find(v) == used.end()) {
            mst.push_back(edges[i]);
            used.insert(u);
            used.insert(v);
        }
    }
    return mst;
}