第二十五章：图(二)：最小生成树与最短路径

图这个结构，说到实际应用，最经典的两个问题就是：怎么修路最省钱，和怎么走最近。

前者对应的是最小生成树，后者对应的是最短路径。

今天咱们就把这两个问题彻底讲透。我会把 Prim、Kruskal、Dijkstra、Floyd 这四个算法，一个一个拆开揉碎了讲。嗯，都是硬骨头，但啃下来之后，你会觉得图也不过如此。

图的核心应用：最小生成树 & 最短路径 最小生成树（MST） Prim 算法 Kruskal 算法 最短路径 Dijkstra 算法 Floyd 算法 Prim：加点法，适合稠密图 Kruskal：加边法，适合稀疏图 Dijkstra：单源最短路径（不能有负权边） Floyd：多源最短路径（允许负权边，不能有负环）

一、最小生成树：怎么修路最省钱？

先说说最小生成树。你想想看，有 n 个城市，要修 n-1 条路把它们全连起来，每条路都有造价。怎么选这 n-1 条路，让总造价最低？

这就是最小生成树要干的事。说白了，就是在一个带权无向图里，找一棵包含所有顶点的树，并且边的权值之和最小。

解决这个问题，有两个经典算法：Prim 和 Kruskal。

1. Prim 算法：加点法

Prim 算法的思路很直观：从一个顶点开始，每次找一条连接「已选顶点集合」和「未选顶点集合」的最短边，把那个新顶点加进来。重复直到所有顶点都加入。

我个人习惯用 Prim 处理稠密图。为什么呢？因为它的时间复杂度是 O(V²)，用二叉堆优化可以降到 O(E log V)。对于边很多的图，Prim 表现很好。

核心思想： 贪心策略，每次选择距离当前生成树最近的顶点。

// Prim 算法核心代码（邻接矩阵版）
#define INF 0x3f3f3f3f
#define MAXV 100

int prim(int graph[MAXV][MAXV], int n) {
    int lowcost[MAXV];  // 记录每个顶点到当前生成树的最小距离
    int visited[MAXV] = {0};
    int sum = 0;
    
    // 从顶点0开始
    visited[0] = 1;
    for (int i = 0; i < n; i++) {
        lowcost[i] = graph[0][i];
    }
    
    for (int i = 1; i < n; i++) {
        // 找最小边
        int min = INF;
        int k = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        if (k == -1) break;  // 图不连通
        sum += min;
        visited[k] = 1;
        
        // 更新 lowcost
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[k][j] < lowcost[j]) {
                lowcost[j] = graph[k][j];
            }
        }
    }
    return sum;
}

小技巧： 如果你用邻接表实现 Prim，记得用优先队列（最小堆）来维护 lowcost，这样每次找最小边就是 O(log V)，整体效率会高很多。

2. Kruskal 算法：加边法

Kruskal 的思路正好反过来。它先把所有边按权值从小到大排序，然后依次选边。选的时候要保证不形成环。

怎么判断是否形成环？用并查集。这是 Kruskal 的精髓所在。

我记得有一次做项目，图特别稀疏，边数远小于 V²。我当时毫不犹豫选了 Kruskal，因为它的时间复杂度是 O(E log E)，对于稀疏图来说，比 Prim 快不少。

// Kruskal 算法核心代码
typedef struct {
    int u, v, w;  // 起点、终点、权值
} Edge;

int parent[MAXV];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

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

int kruskal(Edge edges[], int n, int m) {
    // 按权值排序
    qsort(edges, m, sizeof(Edge), cmp);
    
    for (int i = 0; i < n; i++) parent[i] = i;
    
    int sum = 0, count = 0;
    for (int i = 0; i < m && count < n-1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(u) != find(v)) {
            unionSet(u, v);
            sum += edges[i].w;
            count++;
        }
    }
    return sum;
}

我曾经踩过的坑： 用 Kruskal 时，排序一定要用稳定的排序，或者确保比较函数正确。有一次我写 cmp 时忘了处理权值相等的情况，结果在某些测试用例下排序结果不稳定，导致选边顺序不对，生成了不同的生成树。虽然权值和一样，但调试时差点把我搞疯。

二、最短路径：怎么走最近？

说完修路，咱们再说说导航。从一个城市到另一个城市，怎么走总路程最短？这就是最短路径问题。

这里有两个算法：Dijkstra 解决单源最短路径，Floyd 解决多源最短路径。

1. Dijkstra 算法：单源最短路径

Dijkstra 算法的思路和 Prim 有点像，但目标不同。它维护一个 dist 数组，记录从源点到每个顶点的最短距离。每次从「未确定最短路径」的顶点中，选一个 dist 最小的，然后用它去更新其他顶点。

注意：Dijkstra 不能处理负权边。为什么？因为一旦有负权边，已经确定的最短路径可能被后续的负权边更新，这就破坏了算法的贪心基础。

适用场景： 边权非负的图。如果图中有负权边，请用 Bellman-Ford 或 SPFA。

// Dijkstra 算法核心代码
#define INF 0x3f3f3f3f

void dijkstra(int graph[MAXV][MAXV], int n, int src) {
    int dist[MAXV];
    int visited[MAXV] = {0};
    
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[src] = 0;
    
    for (int i = 0; i < n; i++) {
        // 找未访问的 dist 最小的顶点
        int min = INF, u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        
        if (u == -1) break;
        visited[u] = 1;
        
        // 松弛操作
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF 
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

优化建议： 和 Prim 一样，Dijkstra 也可以用优先队列优化。把 (dist, vertex) 对放入最小堆，每次取堆顶元素。这样时间复杂度可以降到 O((V+E) log V)。

2. Floyd 算法：多源最短路径

Floyd 算法就暴力多了。它用动态规划的思想，三层循环，求出任意两点之间的最短路径。

核心转移方程：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

说白了，就是看从 i 到 j，是直接走近，还是绕道 k 更近。

Floyd 的时间复杂度是 O(V³)，空间复杂度是 O(V²)。所以它只适合顶点数不多的图。我一般在顶点数不超过 200 的时候才用 Floyd，超过这个数，我会考虑用 n 次 Dijkstra。

// Floyd 算法核心代码
void floyd(int graph[MAXV][MAXV], int n) {
    int dist[MAXV][MAXV];
    
    // 初始化
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
    
    // 三层循环
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF
                    && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

注意： Floyd 可以处理负权边，但不能有负权环。如果存在负权环，最短路径会无限小，算法会出问题。判断负权环的方法：跑完 Floyd 后，如果某个 dist[i][i] < 0，说明存在负权环。

三、四个算法的对比总结

算法 解决问题 时间复杂度 适用场景 限制
Prim 最小生成树 O(V²) / O(E log V) 稠密图 无
Kruskal 最小生成树 O(E log E) 稀疏图 无
Dijkstra 单源最短路径 O(V²) / O((V+E) log V) 非负权图 不能有负权边
Floyd 多源最短路径 O(V³) 顶点数少的图 不能有负权环

嗯，这四个算法，每一个都有它自己的脾气。你写代码的时候，一定要想清楚：你的图是稠密还是稀疏？有没有负权边？需要单源还是多源？

想清楚了，选对算法，你的程序就能跑得又快又稳。选错了，轻则效率低下，重则结果错误。

我个人建议，初学者先把 Prim 和 Dijkstra 的朴素版写熟，然后再去研究优化版。Kruskal 的并查集一定要自己手写几遍，面试经常考。Floyd 嘛，背下那三层循环就够了，但要知道它的原理，别只会背代码。

好了，这一章的内容就到这儿。代码多敲几遍，比看十遍都管用。

公众号：蓝海资料掘金营，微信 deep3321
← 上一章 📖 返回目录 下一章 →