最小生成树prim算法C++代码解析

最小生成树Prim算法是一种用于寻找无向图中最短连接边构建一棵包含所有顶点的树的算法。以下是使用C++实现的一个基本版本：

#include <vector>
#include <limits>

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

// 使用优先队列存储待处理的边
using PQueue = std::priority_queue<Edge*, std::vector<Edge*>, std::greater<Edge>>;

// Prim's Algorithm C++
std::vector<Edge> primMST(const std::vector<std::vector<Edge>>& graph) {
    int n = graph.size();
    std::vector<int> visited(n, 0);
    std::vector<Edge*> edges(n * n, nullptr);
    PQueue pq;

    // 初始化：将第一条边（如果有）加入队列
    if (!graph.empty()) {
        edges[0] = &graph[0][0];
        pq.push(edges[0]);
    }

    std::vector<Edge> mst;  // 存储最小生成树的边

    while (!pq.empty()) {
        Edge* currentEdge = pq.top();  // 取出当前最短边
        pq.pop();

        // 如果该边的终点已经访问过，跳过
        if (visited[currentEdge->dest])
            continue;

        visited[currentEdge->dest] = 1;  // 标记为已访问
        mst.push_back(*currentEdge);  // 将边添加到最小生成树中

        // 添加未访问节点的所有边到队列
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                const Edge& newEdge = graph[currentEdge->dest][i];
                if (newEdge.weight < edges[i]->weight) {
                    edges[i] = &newEdge;  // 更新队列中的边
                    pq.push(edges + i);
                }
            }
        }
    }

    return mst;
}