prim和kruskal算法C++

Prim算法和Kruskal算法都是图论中用于寻找最小生成树（Minimum Spanning Tree, MST）的常用算法。以下是它们的基本介绍：

**Prim算法：**
Prim算法是一种贪心策略，它从一个顶点开始，逐步添加边来构建最小生成树。每一步，算法会选择当前未加入树中、连接树中已有顶点的最短边。这个过程通常通过优先队列（如二叉堆）来高效地查找最短边。C++中，可以使用`std::priority_queue`配合邻接矩阵或邻接表数据结构实现。

**Kruskal算法：**
Kruskal算法则采用分治的思想，首先将所有边按权重排序，然后从小到大依次尝试加入边。如果这条边不会形成环，则将其加入到生成树中。由于需要检测是否形成环，所以常常使用并查集数据结构来维护连通性。C++中，可以用`std::vector<bool>`标记每个边所在的集合，并使用`std::set`存储边的优先级。

以下是C++代码示例的大致框架：

// Prim算法
std::vector<int> prim(std::vector<std::pair<int, int>>& edges, std::vector<bool>& graph) {
    // 初始化...
}

// Kruskal算法
std::vector<int> kruskal(std::vector<std::pair<int, int>>& edges) {
    std::sort(edges.begin(), edges.end()); // 按权重排序
    std::vector<int> mst; // 存储最小生成树的边
    union_find uf; // 并查集

    for (const auto& edge : edges) {
        if (!uf.connected(edge.first, edge.second)) { // 如果不构成环
            uf.union_set(edge.first, edge.second);
            mst.push_back(edge.first); // 添加边
        }
    }

    return mst;
}