求图的最小生成树C++

在计算机科学中，求解图的最小生成树是指找到一棵包含图中所有顶点且边权之和最小的有向或无向树。最著名的算法之一是Prim's算法和Kruskal's算法。

**Prim's算法** (也叫Prim-Jarnik算法) 是从一个初始顶点开始，逐步添加与当前生成树相连且权重最小的边，直到覆盖所有顶点。C++实现通常包括一个优先队列用于存储边，以及邻接矩阵或邻接表数据结构。

#include <vector>
#include <queue>

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

class PrimMST {
public:
    // 构造函数初始化空集合，并设置起点的权重为0
    PrimMST(int start, vector<Edge>& edges)
        : mst_weight(0), visited(start, false), graph(edges) {}

    // 计算最小生成树并返回总权重
    int getMSTWeight() { return mst_weight; }

private:
    std::vector<bool> visited;
    std::vector<int> parent;

    void addEdgeToMST(int u, int v) {
        mst_weight += graph[u].weight;
        parent[v] = u;
    }

    void relax(int u, int v) {
        if (!visited[v] && graph[u].weight < graph[parent[v]].weight) {
            parent[v] = u;
        }
    }

    // 主循环，不断寻找新的边加入最小生成树
    void findNextNode() {
        for (int i = 0; i < graph.size(); ++i) {
            if (!visited[i]) {
                relax(current_node, i);
                if (parent[i] != -1)
                    addEdgeToMST(current_node, i);
            }
        }
    }

    int current_node; // 当前已处理的节点

    // 初始化
    void initialize() {
        current_node = start;
        visited[start] = true;
        parent.resize(graph.size(), -1); // 父节点数组默认值为-1
    }

    int mst_weight; // 最小生成树的权重
    std::vector<Edge> graph; // 图的边列表
};

**Kruskal's算法** 则是将图的所有边按权重从小到大排序，然后依次尝试加入，如果新加入的边不会形成环，则继续，直到所有顶点都被连接上。这个过程可以用并查集数据结构来维护连通性。