Prim算法C语言实现如何保证最小生成树最优性？

【全网首发】手把手带你搞定最小生成树Prim算法，C语言实现详解与代码剖析

** 在图论中，最小生成树（Minimum Spanning Tree, MST）是一个经典问题，而Prim算法正是求解带权连通图的最小生成树的高效算法之一，本文将以通俗易懂的方式，结合C语言详细讲解Prim算法的原理、步骤，并提供完整可运行的C语言代码及详细解析，助你彻底掌握这一重要算法。

什么是最小生成树（MST）？

在学习Prim算法之前,我们首先要明确什么是最小生成树。

• 生成树（Spanning Tree）： 一个连通图的生成树是其包含图中所有顶点的极小连通子图，所谓“极小”，意味着移除其中任意一条边，都会导致子图不再连通，一个有n个顶点的连通图的生成树有n-1条边。
• 最小生成树（Minimum Spanning Tree, MST）： 对于一个带权连通图（即边带有权值的图），其所有生成树中，使得所有边的权值之和最小的那棵生成树，称为最小生成树。

MST的应用场景非常广泛，

• 通信网络设计： 在n个城市之间建立通信网络，要求任意两个城市都能互通，且总建设成本（边的权值）最低。
• 电路设计： 连接电路板上多个接点，使得总连线长度最短。
• 交通规划： 连接多个城镇，使得道路建设总成本最低。

Prim算法核心思想

Prim算法是一种贪心算法，其核心思想可以概括为：从一个起始顶点开始，逐步将图的顶点和边加入到生成树中，每次选择一条连接已加入生成树的顶点与未加入生成树的顶点的权值最小的边，直到所有顶点都包含在生成树中。

形象比喻： 想象你在一片森林中（图的顶点），你有一个营地（已加入生成树的顶点集合），你每次都从营地出发，找到距离最近的一棵树（未加入生成树的顶点），并修建一条最短的路径（权值最小的边）将其连接到营地，随着营地的不断扩大，最终所有树都会被连接起来，形成一片完整的森林（最小生成树），且你修建的所有路径总长度最短。

Prim算法步骤详解

假设我们有一个带权连通图G = (V, E)，其中V是顶点集合，E是边集合，prim算法的步骤如下：

1. 初始化：

   • 选择一个起始顶点 v0，将其加入生成树顶点集合 U（初始时 U = {v0}）。
   • 生成树边集合 TE 为空。
   • 对于每个顶点 v 属于 V - U（未加入生成树的顶点），初始化一个辅助数组 key[v]，表示 v 到 U 中顶点的最小边的权值，初始时，key[v0] = 0（因为 v0 已经在 U 中），对于其他顶点 v，key[v] 为 v 到 v0 的边的权值（如果存在），或为一个很大的数（表示不可达）。
   • 初始化一个辅助数组 parent[v]，用于记录顶点 v 在生成树中的前驱（即通过哪个顶点连接到 U）。

2. 重复以下步骤，直到 U 包含所有顶点 V：

   • 在 V - U 中找到顶点 u，使得 key[u] 的值最小。
   • 将 u 加入集合 U。
   • 将连接 u 和其前驱 parent[u] 的边 (parent[u], u) 加入生成树边集合 TE。
   • 对于 u 的所有邻接顶点 v（即存在边 (u, v)）：
     • v 不在 U 中，并且边 (u, v) 的权值小于 key[v]：
       • 更新 key[v] = weight(u, v)。
       • 更新 parent[v] = u。

3. 结束：

   
   （图片来源网络，侵删）
   • 当 U = V 时，算法结束。TE 中包含的n-1条边就构成了图G的最小生成树。

Prim算法的C语言实现与代码解析

下面我们通过一个具体的例子来演示Prim算法的C语言实现。

示例图： 假设有以下一个带权无向图（邻接矩阵表示）：

顶点: 0, 1, 2, 3, 4
邻接矩阵:
   0  1  2  3  4
0 0  2  0  6  0
1 2  0  3  8  5
2 0  3  0  0  7
3 6  8  0  0  9
4 0  5  7  9  0

C语言代码实现：

#include <stdio.h>
#include <limits.h> // 用于INT_MAX
#define V 5 // 顶点数量
// 查找key值最小的顶点，该顶点不在mstSet中
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
// 打印构建的最小生成树
void printMST(int parent[], int graph[V][V]) {
    printf("Edge   Weight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
    }
}
// Prim算法实现
void primMST(int graph[V][V]) {
    int parent[V]; // 存储构建的最小生成树
    int key[V];    // 存储连接到最小生成树的最小边权值
    bool mstSet[V]; // 标记顶点是否已经包含在最小生成树中
    // 初始化所有key值为无穷大，mstSet[]为false
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    // 第一个顶点总是包含在最小生成树中
    key[0] = 0;     // 使第一个顶点成为根
    parent[0] = -1; // 第一个顶点没有父节点
    // 构建V-1条边的最小生成树
    for (int count = 0; count < V - 1; count++) {
        // 从未包含在mstSet中的顶点中选择key值最小的顶点
        int u = minKey(key, mstSet);
        // 将选定的顶点u加入mstSet
        mstSet[u] = true;
        // 更新与u相邻的顶点的key值和parent数组
        for (int v = 0; v < V; v++) {
            // graph[u][v]是非零的，表示u和v之间有边
            // mstSet[v]为false，表示v还没有包含在最小生成树中
            // graph[u][v] < key[v]，表示找到了更小的权值
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    // 打印构建的最小生成树
    printMST(parent, graph);
}
int main() {
    /* 示例图 */
    int graph[V][V] = {
        {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}
    };
    printf("Prim算法构建的最小生成树为：\n");
    primMST(graph);
    return 0;
}

代码解析：

1. #include <limits.h>: 引入该头文件是为了使用 INT_MAX 宏，它表示 int 类型的最大值，通常用于初始化key值为“无穷大”。
2. #define V 5: 定义图的顶点数量，方便修改。
3. minKey(int key[], bool mstSet[]):
   • 此函数用于在尚未加入最小生成树的顶点（mstSet[v] == false）中，找到key值（即到已加入生成树的顶点的最小边权值）最小的顶点。
   • 返回该最小key值对应的顶点索引。
4. printMST(int parent[], int graph[V][V]):
   • 此函数用于打印最终构建的最小生成树。
   • parent 数组记录了每个顶点（除根节点外）在生成树中的父节点，通过遍历 parent 数组即可得到所有边。
   • graph 数组用于获取边的权值。
5. primMST(int graph[V][V]):
   • 这是Prim算法的核心实现函数。
   • 初始化：parent 数组初始化为-1（根节点无父节点），key 数组初始化为 INT_MAX（表示初始时所有顶点到生成树的距离为无穷大），mstSet 数组初始化为 false（表示所有顶点都未加入生成树）。
   • 选择起始顶点：将顶点0的key值设为0，这样 minKey 函数第一次就会选择顶点0作为起点。
   • 主循环：循环 V-1 次，每次选择一个顶点加入生成树。
     • int u = minKey(key, mstSet);：选择当前key值最小的顶点 u。
     • mstSet[u] = true;：将 u 标记为已加入生成树。
     • 更新key值：遍历所有顶点 v，v 与 u 相邻（graph[u][v] != 0），且 v 未加入生成树（mstSet[v] == false），并且通过 u 到达 v 的边权值比当前 key[v] 更小，则更新 key[v] = graph[u][v] 和 parent[v] = u，这一步是贪心策略的体现，总是保留到生成树的最小边。
6. main():
   • 定义示例图的邻接矩阵。
   • 调用 primMST(graph) 函数计算并打印最小生成树。

程序输出：

Prim算法构建的最小生成树为：
Edge   Weight
0 - 1    2 
1 - 2    3 
1 - 4    5 
0 - 3    6 

总权值 = 2 + 3 + 5 + 6 = 16。

Prim算法的时间复杂度分析

Prim算法的时间复杂度取决于我们如何实现 minKey 函数以及如何更新key值。

1. 邻接矩阵表示：

   • minKey 函数需要遍历所有顶点来找到最小key值，这部分的时间复杂度为 O(V)。
   • 主循环执行 V-1 次，每次调用 minKey (O(V))，并且还要遍历所有顶点的邻接点（对于邻接矩阵，这是 O(V)）。
   • 总的时间复杂度为 O(V^2)。
   • 适用场景：适用于边数较多（稠密图）的情况。

2. 邻接表表示 + 优先队列（最小堆）：

   • 使用邻接表存储图,可以更高效地找到某个顶点的所有邻接点。
   • 使用最小堆（优先队列）来存储key值，可以在 O(log V) 时间内找到并删除最小key值的顶点。
   • 当更新某个顶点的key值时,可以在 O(log V) 时间内进行堆调整。
   • 在这种实现下,总的时间复杂度为 O(E + V log V)，其中E是边的数量。
   • 适用场景：适用于边数较少（稀疏图）的情况。

| 实现方式 | 时间复杂度 | 适用场景 | | :------------- | :--------- | :------------- | | 邻接矩阵 | O(V^2) | 稠密图 | | 邻接表+优先队列 | O(E + V log V) | 稀疏图 |

Prim算法 vs. Kruskal算法

Prim算法是求解最小生成树的另一个经典算法,简单对比一下：

选择哪种算法取决于图的稀疏程度和具体实现需求。

总结与展望

本文详细介绍了最小生成树的概念、Prim算法的核心思想、具体步骤，并通过C语言实现了基于邻接矩阵的Prim算法，同时对代码进行了逐行解析，我们还分析了Prim算法的时间复杂度，并将其与Kruskal算法进行了简要对比。

掌握Prim算法对于理解贪心策略、图论算法以及解决实际问题都具有重要意义，希望本文能帮助你彻底搞懂Prim算法的C语言实现，如果你有任何疑问或建议，欢迎在评论区留言交流！

后续学习方向：

• 尝试用邻接表+优先队列（如C++的priority_queue或手动实现最小堆）来优化Prim算法的实现。
• 深入学习Kruskal算法及其并查集数据结构。
• 探索最小生成树的其他变种或应用场景。

最小生成树, Prim算法, C语言, 图论, 贪心算法, 数据结构, 邻接矩阵, 最小生成树算法, C语言实现, 算法解析, 稠密图, 代码示例, 百度搜索, 程序员面试