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

求解最小生成树的两种经典算法

主要有两种算法：

1. Prim算法：从一个顶点出发，逐步扩展生成树；
2. Kruskal算法：按边的权重从小到大依次选择，避免形成环。

本文重点讲解 Prim算法，因为它更适合用邻接矩阵表示的图，且逻辑清晰，非常适合初学者理解。

Prim算法原理（小白也能懂！）

Prim算法的核心思想是“贪心”——每一步都选择当前能连接到生成树的最短边。

步骤如下：

1. 任选一个起始顶点，加入生成树集合；
2. 找出所有一端在生成树内、另一端在生成树外的边中权重最小的一条；
3. 将这条边的外部顶点加入生成树；
4. 重复步骤2-3，直到所有顶点都被包含。

C语言实现Prim算法

下面我们用C语言编写一个完整的Prim算法程序。我们使用邻接矩阵来表示图。

// C语言最小生成树 - Prim算法实现#include <stdio.h>#include <limits.h>#define V 5  // 顶点数量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");    for (int i = 1; i < V; i++)        printf("%d - %d\t\t%d\n", parent[i], i, graph[i][parent[i]]);}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;         // 起始顶点    parent[0] = -1;     // 第一个节点无父节点    // 构建MST    for (int count = 0; count < V - 1; count++) {        int u = minKey(key, mstSet);        mstSet[u] = 1;        // 更新相邻顶点的key值        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() {    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;}

代码说明

• key[] 数组记录每个顶点到当前生成树的最小边权重；
• mstSet[] 标记顶点是否已加入MST；
• parent[] 记录MST中每个节点的父节点，用于输出结果；
• 主循环执行 V-1 次（因为生成树有 V-1 条边）。

运行上述程序，你将看到输出的最小生成树的边及其权重总和最小。

总结

通过本教程，你已经掌握了C语言最小生成树的基本概念和Prim算法的实现方法。这是C语言图论中的重要内容，也是面试和项目开发中的常见考点。

如果你想进一步提升，可以尝试：

• 用邻接表优化空间复杂度；
• 实现Kruskal算法（需要用到并查集）；
• 处理不连通图的情况（此时不存在生成树）。

希望这篇关于最小生成树实现的教程对你有所帮助！动手敲一遍代码，你会理解得更深刻。