Prim算法详解（C++语言实现最小生成树的完整教程）

什么是Prim算法？

Prim算法由数学家Robert C. Prim于1957年提出，其核心思想是：从一个起始顶点开始，每次选择与当前生成树相连且权重最小的边，将其加入生成树，直到包含所有顶点为止。

该算法属于图论算法中的基础内容，广泛应用于网络设计、电路布线、聚类分析等领域。

Prim算法的基本步骤

1. 初始化：选择任意一个顶点作为起始点，将其加入最小生成树集合。
2. 维护一个“候选边”集合：包含所有一端在生成树内、另一端在生成树外的边。
3. 从候选边中选择权重最小的边，将其连接的外部顶点加入生成树。
4. 重复步骤2-3，直到所有顶点都被包含。

C++实现Prim算法

我们将使用邻接矩阵表示图，并借助优先队列（最小堆）优化边的选择过程。以下是完整的C++代码：

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;// 定义边结构体struct Edge {    int to;          // 目标顶点    int weight;      // 边的权重        // 重载小于号，用于优先队列（最小堆）    bool operator>(const Edge& other) const {        return weight > other.weight;    }};// Prim算法主函数vector<pair<int, int>> prim(const vector<vector<int>>& graph, int start) {    int n = graph.size();    vector<bool> inMST(n, false);                     // 标记顶点是否已在MST中    vector<int> minEdge(n, INT_MAX);                  // 到MST的最小边权重    vector<int> parent(n, -1);                        // 记录MST中的父节点    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;        // 初始化起始点    minEdge[start] = 0;    pq.push({start, 0});        vector<pair<int, int>> mstEdges;  // 存储最终的MST边        while (!pq.empty()) {        Edge current = pq.top();        pq.pop();        int u = current.to;                // 如果该顶点已处理过，跳过        if (inMST[u]) continue;                inMST[u] = true;                // 如果不是起始点，添加边到结果        if (parent[u] != -1) {            mstEdges.push_back({parent[u], u});        }                // 遍历所有邻接顶点        for (int v = 0; v < n; ++v) {            if (graph[u][v] != 0 && !inMST[v]) {                if (graph[u][v] < minEdge[v]) {                    minEdge[v] = graph[u][v];                    parent[v] = u;                    pq.push({v, graph[u][v]});                }            }        }    }        return mstEdges;}// 主函数：测试Prim算法int main() {    // 示例图（邻接矩阵）    vector<vector<int>> graph = {        {0, 2, 0, 6, 0},        {2, 0, 3, 8, 5},        {0, 3, 0, 0, 7},        {6, 8, 0, 0, 9},        {0, 5, 7, 9, 0}    };        int startVertex = 0;    vector<pair<int, int>> mst = prim(graph, startVertex);        cout << "最小生成树的边为：\n";    for (auto& edge : mst) {        cout << edge.first << " - " << edge.second << "\n";    }        return 0;}

代码说明

• Edge结构体：用于存储目标顶点和边权重，并重载 > 运算符以便在优先队列中按权重排序。
• inMST数组：记录每个顶点是否已加入最小生成树。
• minEdge数组：记录每个顶点到当前MST的最小边权重。
• 优先队列：自动维护最小权重边，提升效率（时间复杂度为 O(E log V)）。

为什么学习Prim算法？

掌握Prim算法不仅能帮助你理解图论中的核心思想，还能为后续学习更复杂的算法（如Dijkstra、Kruskal等）打下坚实基础。无论你是准备面试、参加竞赛，还是开发实际项目，这项技能都极具价值。

总结

通过本教程，我们详细讲解了Prim算法的原理，并用C++语言实现了完整的最小生成树求解程序。希望你能动手运行代码、修改图结构，加深理解。记住，算法学习的关键在于实践！

如果你觉得这篇Prim算法教程对你有帮助，欢迎分享给更多正在学习图论算法的朋友！