C++求解最小生成树

在C++中，求解最小生成树通常使用Prim算法或Kruskal算法。这里我们简单介绍Prim算法：

**Prim算法**是一种贪心算法，它从图的一个顶点开始，逐步添加边，每次选择当前未加入的边中，连接到已形成树的新节点的那个边，使得树的总权重最小。Prim算法的基本步骤如下：

1. 初始化：选择任意一个顶点作为初始集合S，其余顶点为非S集合V-S。
2. 找最短边：在S和V-S之间找到权值最小的边，并将这条边所连接的不在S集合的顶点加入S。
3. 更新：更新所有新加入顶点与当前S之间的边，继续查找并加入新的顶点，直到所有顶点都在S内。
4. 结果：剩下的边就构成了最小生成树。

**使用C++实现**：

#include <vector>
#include <queue>

struct Edge {
    int src, dest, weight;
};

class PrimMST {
private:
    std::vector<Edge> edges;
    std::vector<bool> visited;
    std::vector<int> parent; // 最小生成树中的前驱

public:
    PrimMST(std::vector<Edge>& e) : edges(e) {}

    void prim() {
        visited.assign(edges.size(), false);
        int n = edges.size();
        parent.resize(n, -1); // 根节点的parent设为-1

        int start_index = 0; // 首选任意一个节点
        visited[start_index] = true;

        for (int count = 0; count < n - 1; ++count) {
            int u = findMin(); // 寻找下一个节点
            for (auto edge : edges) {
                if (!visited[edge.dest] && edge.weight < edges[parent[edge.dest]].weight) {
                    parent[edge.dest] = edge.src;
                }
            }
        }
    }

    int findMin() { // 查找未访问且与已访问节点相连的最小边的源端点
        int min_val = INT_MAX, min_idx;
        for (size_t i = 0; i < edges.size(); ++i) {
            if (!visited[i] && edges[i].weight < min_val) {
                min_val = edges[i].weight;
                min_idx = i;
            }
        }
        return min_idx;
    }
};