一、图的最小生成树：从概念到实战

图的最小生成树，说白了就是在一个带权连通图中，找出一棵包含所有顶点的树，并且这棵树的边权总和最小。嗯，这个概念听起来简单，但实际应用可太广了——比如城市间铺设光缆、电路板布线、管道网络规划，我这些年做嵌入式项目，至少遇到过三四次需要用到最小生成树的场景。

先说说生成树的概念。一个连通图可能有多个生成树，每个生成树都包含原图的所有顶点，但边数刚好是顶点数减一。为什么是顶点数减一？因为树结构嘛，n个节点需要n-1条边才能连通，多一条就成环了。

1.1 生成树的数学定义

设G=(V,E)是一个连通无向图，其中V是顶点集合，E是边集合。如果T是G的一个子图，满足：

• T包含G中所有顶点
• T是连通的
• T没有回路

那么T就是G的一棵生成树。权值和最小的那棵，就是最小生成树。

我记得刚入行时，有个同事把生成树和最短路径搞混了。两者区别很大：最短路径关注的是两个点之间的最优路径，而最小生成树关注的是全局连通的最优方案。你想想看，如果只是让两个城市通光缆，那用Dijkstra就行；但要让所有城市都通上，就得用最小生成树了。

二、Prim算法：加点法

Prim算法的思路很直观——从一个顶点开始，每次选择一条连接「已选顶点集合」和「未选顶点集合」的最小权值边，把这个新顶点加进来。说白了就是「贪心地往外扩张」。

2.1 算法步骤

1. 任选一个起始顶点，加入集合U
2. 在连接U和V-U的边中，找权值最小的那条
3. 把这条边对应的新顶点加入U
4. 重复步骤2-3，直到U包含所有顶点

2.2 代码实现

我用C语言实现了一个基于邻接矩阵的Prim算法。这里用了两个辅助数组：lowcost记录到U的最小边权，adjvex记录对应的顶点。

#define INF 65535
#define MAXV 100

// 邻接矩阵存储图
typedef struct {
    int edges[MAXV][MAXV];
    int n;  // 顶点数
} MGraph;

void Prim(MGraph *G, int start) {
    int lowcost[MAXV];  // 保存到U的最小权值
    int adjvex[MAXV];   // 保存对应顶点
    int i, j, k, min;
    
    // 初始化：从start开始
    for (i = 0; i < G->n; i++) {
        lowcost[i] = G->edges[start][i];
        adjvex[i] = start;
    }
    lowcost[start] = 0;  // start已加入U
    
    for (i = 1; i < G->n; i++) {
        // 找最小权值边
        min = INF;
        j = 0;
        while (j < G->n) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        
        // 输出这条边
        printf("(%d, %d) weight=%d\n", adjvex[k], k, min);
        lowcost[k] = 0;  // 加入U
        
        // 更新lowcost
        for (j = 0; j < G->n; j++) {
            if (lowcost[j] != 0 && G->edges[k][j] < lowcost[j]) {
                lowcost[j] = G->edges[k][j];
                adjvex[j] = k;
            }
        }
    }
}

2.3 时间复杂度分析

上面这个实现是O(V²)的，因为每次找最小边都要扫描整个数组。如果用二叉堆优化，可以降到O(E log V)。我个人习惯在顶点数少于100时直接用数组版本，代码简单，不容易出bug。

三、Kruskal算法：加边法

Kruskal的思路正好反过来——先把所有边按权值排序，然后从小到大依次选边，只要不形成回路就加入。这就像在修路时，先修成本最低的路段，但得保证不会修成环路。

3.1 算法步骤

1. 将所有边按权值从小到大排序
2. 初始化一个空集合T
3. 遍历排序后的边，如果加入后不形成回路，就加入T
4. 当T中有V-1条边时停止

3.2 关键问题：如何判断回路？

这里要用到并查集（Union-Find）。每条边加入前，检查两个端点是否在同一个集合中。如果在，说明已经连通，加入就会形成回路；如果不在，就合并两个集合。

// 并查集实现
int parent[MAXV];

int find(int x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

void unionSet(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx != ry)
        parent[ry] = rx;
}

// 边结构
typedef struct {
    int u, v;   // 两个顶点
    int weight; // 权值
} Edge;

// 比较函数，用于qsort
int cmp(const void *a, const void *b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

void Kruskal(Edge edges[], int n, int e) {
    int i, count = 0;
    
    // 初始化并查集
    for (i = 0; i < n; i++)
        parent[i] = i;
    
    // 排序
    qsort(edges, e, sizeof(Edge), cmp);
    
    for (i = 0; i < e && count < n-1; i++) {
        int ru = find(edges[i].u);
        int rv = find(edges[i].v);
        
        if (ru != rv) {  // 不会形成回路
            printf("(%d, %d) weight=%d\n", edges[i].u, edges[i].v, edges[i].weight);
            unionSet(ru, rv);
            count++;
        }
    }
}

3.3 时间复杂度

Kruskal的主要开销在排序上，O(E log E)。并查集操作近似O(1)。所以整体复杂度是O(E log E)。对于边稀疏的图，Kruskal比Prim快很多。

四、两种算法的比较

这两种算法各有千秋，我根据自己的项目经验总结了一张对比表：

对比维度	Prim算法	Kruskal算法
核心思想	加点法，逐步扩张	加边法，全局筛选
数据结构依赖	邻接矩阵或邻接表	边集数组 + 并查集
时间复杂度	O(V²) 或 O(E log V)	O(E log E)
适用场景	稠密图（边多）	稀疏图（边少）
实现难度	中等，逻辑直观	稍高，需并查集
内存占用	邻接矩阵较大	边集数组较小

我个人习惯这样选：如果顶点数少（比如几十个），用Prim的邻接矩阵版本，代码简单好调试。如果边数远少于顶点数的平方，用Kruskal更省内存。有一次我在一个STM32项目上处理传感器网络布线，顶点只有32个，但边有200多条，我用了Kruskal，因为并查集实现起来很轻量。

五、知识体系总览

下面这张图展示了本章的核心知识结构，我把它画成了流程图，方便你理解整体脉络：

---

公众号：蓝海资料掘金营，微信deep3321