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

Prim 算法原理（适合稠密图）

Prim 算法是一种贪心算法，它的基本思想是：

1. 从任意一个顶点开始，将其加入生成树集合。
2. 每次选择一条连接“已选顶点”和“未选顶点”的最小权重边，将新顶点加入集合。
3. 重复第2步，直到所有顶点都被包含。

Prim 算法特别适合用邻接矩阵表示的图，时间复杂度为 O(V²)，其中 V 是顶点数。

C语言实现 Prim 算法

下面是一个完整的 C 语言代码示例，使用邻接矩阵存储图，并输出最小生成树的边及总权重。

#include <stdio.h>#include <limits.h>#define V 5  // 顶点数量// 找到 key[] 中最小且不在 mstSet 中的顶点int minKey(int key[], int mstSet[]) {    int min = INT_MAX, min_index;    for (int v = 0; v < V; v++)        if (mstSet[v] == 0 && key[v] < min)            min = key[v], min_index = v;    return min_index;}// 打印最小生成树void printMST(int parent[], int graph[V][V]) {    printf("边\t\t权重\n");    int totalWeight = 0;    for (int i = 1; i < V; i++) {        printf("%d - %d\t\t%d\n", parent[i], i, graph[i][parent[i]]);        totalWeight += graph[i][parent[i]];    }    printf("最小生成树总权重: %d\n", totalWeight);}// Prim 算法主函数void primMST(int graph[V][V]) {    int parent[V];   // 存储 MST 的父节点    int key[V];      // 用于选取最小权重边    int mstSet[V];   // 标记顶点是否已加入 MST    // 初始化    for (int i = 0; i < V; i++)        key[i] = INT_MAX, mstSet[i] = 0;    key[0] = 0;       // 从顶点 0 开始    parent[0] = -1;   // 第一个节点无父节点    for (int count = 0; count < V - 1; count++) {        int u = minKey(key, mstSet);        mstSet[u] = 1;        for (int v = 0; v < V; v++)            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])                parent[v] = u, key[v] = graph[u][v];    }    printMST(parent, graph);}int main() {    /* 示例图（邻接矩阵）       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]    */    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}    };    primMST(graph);    return 0;}

代码说明

• key[]：记录每个顶点到当前 MST 的最小边权重。
• mstSet[]：布尔数组，标记顶点是否已加入 MST。
• parent[]：记录 MST 中每个顶点的父节点，用于重建树结构。

运行上述代码，你会看到类似以下输出：

边		权重0 - 1		21 - 2		30 - 3		61 - 4		5最小生成树总权重: 16

为什么学习 C语言最小生成树？

掌握 C语言图论 基础不仅能帮助你通过算法面试，还能提升对底层数据结构的理解。Prim 算法作为 最小生成树实现 的核心方法之一，是学习更高级图算法（如 Dijkstra、Kruskal）的重要基石。

小结

本教程详细讲解了如何用 C 语言实现 Prim 算法来求解最小生成树。我们从概念出发，逐步深入到代码实现，并配有完整可运行的示例。希望你现在对 C语言最小生成树、Prim算法、C语言图论 和 最小生成树实现 有了清晰的理解！

动手试试修改图的邻接矩阵，观察不同输入下 MST 的变化吧！