C++最小生成树算法详解（从零开始掌握Prim算法与图论基础）

Prim算法原理

Prim算法是一种贪心算法，用于求解C++最小生成树。它的基本思想是：

1. 从任意一个顶点开始，将其加入MST集合。
2. 在所有连接MST集合与非MST集合的边中，选择权重最小的边，并将该边连接的新顶点加入MST集合。
3. 重复第2步，直到所有顶点都被包含在MST中。

C++实现Prim算法

下面我们将用C++编写一个完整的Prim算法程序。为了简化，我们使用邻接矩阵来表示图。

#include <iostream>#include <vector>#include <climits>using namespace std;// Prim算法实现void primMST(vector<vector<int>>& graph, int V) {    // key[i] 表示顶点i到MST的最小边权重    vector<int> key(V, INT_MAX);    // inMST[i] 表示顶点i是否已在MST中    vector<bool> inMST(V, false);    // parent[i] 记录MST中顶点i的父节点    vector<int> parent(V, -1);    // 从顶点0开始    key[0] = 0;    for (int count = 0; count < V - 1; count++) {        // 找到key最小且不在MST中的顶点        int u = -1;        for (int v = 0; v < V; v++) {            if (!inMST[v] && (u == -1 || key[v] < key[u]))                u = v;        }        // 将u加入MST        inMST[u] = true;        // 更新u的所有邻接顶点的key值        for (int v = 0; v < V; v++) {            if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {                parent[v] = u;                key[v] = graph[u][v];            }        }    }    // 输出最小生成树    cout << "边\t权重\n";    for (int i = 1; i < V; i++) {        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << "\n";    }}int main() {    // 示例图：5个顶点    int V = 5;    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}    };    cout << "C++最小生成树（Prim算法）结果：\n";    primMST(graph, V);    return 0;}

代码解析

上述代码实现了Prim算法的核心逻辑：

• key数组记录每个顶点到当前MST的最小边权重。
• inMST数组标记顶点是否已加入MST。
• 每次循环选择key最小的未加入顶点，并更新其邻居的key值。

运行结果将输出最小生成树的边及其权重。这个实现的时间复杂度为 O(V²)，适用于稠密图。对于稀疏图，可以使用优先队列（堆）优化至 O(E log V)。

总结

通过本教程，你已经掌握了如何用C++语言实现最小生成树的Prim算法。这是C++图论中的基础但极其重要的内容。无论你是准备面试还是学习算法，理解并能手写最小生成树实现都是必备技能。

建议你动手运行上面的代码，修改图的结构，观察输出变化，加深理解。祝你在算法学习的道路上越走越远！