第二十八讲：图（二）——最小生成树、最短路径与拓扑排序

好，咱们继续聊图。上一讲我们把图的基本结构、遍历方式都过了一遍。这一讲，我们要解决几个更实际的问题——怎么修路最省钱？怎么走最近？怎么安排任务最合理？这些都是图论里的经典问题，也是面试和工程中的常客。

一、最小生成树：怎么用最少的钱连通所有节点？

先想一个场景。你是一个小镇的规划师，要在几个村子之间修路。目标是让所有村子都能互通，但修路要花钱，你希望总成本最低。这就是最小生成树（MST）要解决的问题。

最小生成树，说白了就是在一个带权无向连通图里，找一棵树，包含所有顶点，并且边的权值之和最小。注意，是树，所以不能有环。

解决这个问题，有两个经典算法：Prim 和 Kruskal。我当年刚学的时候，总觉得它们差不多，后来在项目中用多了才发现，各有各的脾气。

1. Prim 算法：从一个点开始“生长”

Prim 算法的思路很直观：随便选一个起点，然后每次从当前已选中的顶点集合出发，找一条最短的边，把对端的顶点拉进来。重复，直到所有顶点都进来。

你可以把它想象成“滚雪球”。从一个点开始，每次把离雪球最近的那个点粘进来。

我习惯用邻接矩阵来实现 Prim，因为代码写起来很清晰。当然，如果图很稀疏，用邻接表加优先队列会更高效。

// Prim 算法核心代码（邻接矩阵版）
#define INF 0x3f3f3f3f
int prim(int n, int graph[][n]) {
    int lowcost[n]; // 记录每个顶点到当前树的最小距离
    int visited[n] = {0};
    int sum = 0;

    // 初始化：从顶点0开始
    for (int i = 0; i < n; i++) {
        lowcost[i] = graph[0][i];
    }
    visited[0] = 1;

    for (int i = 1; i < n; i++) {
        // 找当前最小的边
        int min = INF, minIdx = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                minIdx = j;
            }
        }
        if (minIdx == -1) break; // 图不连通
        sum += min;
        visited[minIdx] = 1;

        // 更新 lowcost
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIdx][j] < lowcost[j]) {
                lowcost[j] = graph[minIdx][j];
            }
        }
    }
    return sum;
}

2. Kruskal 算法：按边排序，逐个加入

Kruskal 的思路完全不同。它先把所有边按权值从小到大排序，然后依次取出，只要这条边不会形成环，就把它加入生成树。

这里的关键是“判环”。怎么判断加入一条边会不会形成环？用并查集。我刚开始学的时候，觉得并查集很绕，后来写了几次才发现，它其实就是给每个节点找个“老大”，如果两个节点的老大是同一个，说明它们已经在同一个集合里了，再加边就会成环。

// Kruskal 算法核心代码（并查集实现）
typedef struct {
    int u, v, w;
} Edge;

int cmp(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

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

void unionSet(int parent[], int rank[], int x, int y) {
    int rx = find(parent, x);
    int ry = find(parent, y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rank[rx]++; }
}

int kruskal(int n, Edge edges[], int m) {
    qsort(edges, m, sizeof(Edge), cmp);
    int parent[n], rank[n] = {0};
    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 ru = find(parent, edges[i].u);
        int rv = find(parent, edges[i].v);
        if (ru != rv) {
            unionSet(parent, rank, ru, rv);
            sum += edges[i].w;
            count++;
        }
    }
    return sum;
}

Kruskal 适合边稀疏的图。因为它的复杂度主要取决于排序，O(E log E)，E 是边数。如果边很少，它比 Prim 快很多。

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

最小生成树解决的是“连通所有点”的问题。但更多时候，我们想知道“从 A 到 B 怎么走最近”。这就是最短路径问题。

两个经典算法：Dijkstra 和 Floyd。一个求单源最短路径，一个求所有点对之间的最短路径。

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

Dijkstra 的思路和 Prim 有点像，也是“滚雪球”。但它记录的是从起点到每个顶点的最短距离，而不是到当前树的最小边。

它要求图中不能有负权边。为什么？因为如果有负权边，已经确定的最短距离可能会被后面更小的值更新，Dijkstra 的贪心策略就失效了。

// Dijkstra 算法（邻接矩阵版）
void dijkstra(int n, int graph[][n], int start) {
    int dist[n];
    int visited[n] = {0};
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[start] = 0;

    for (int i = 0; i < n; i++) {
        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];
            }
        }
    }
}

2. Floyd 算法：所有点对最短路径

Floyd 算法就暴力多了。它用动态规划的思想，三层循环，直接算出所有点对之间的最短距离。

代码极其简洁，但复杂度是 O(n³)。所以它只适合节点数很少的图（比如 n < 200）。

// Floyd 算法
void floyd(int n, int graph[][n]) {
    int dist[n][n];
    // 初始化
    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

你想想看，这个算法为什么能处理负权边？因为它不是贪心，而是把所有可能的中间节点都试了一遍。但它不能处理负权环，因为如果有负权环，最短路径可以无限小。

三、拓扑排序与关键路径

这两个问题针对的是有向无环图（DAG）。拓扑排序解决的是“谁先谁后”的问题，关键路径解决的是“整个工程最短需要多久”的问题。

1. 拓扑排序：有依赖关系的任务排序

比如你要修一门课，必须先修完前置课程。拓扑排序就是把这些课程排成一个线性序列，使得每个课程都在它的前置课程之后。

实现方式有两种：Kahn 算法（基于入度）和 DFS 法。我个人更喜欢 Kahn 算法，因为它直观，而且能检测环。

// Kahn 算法实现拓扑排序
int topologicalSort(int n, int indegree[], int adj[][n]) {
    int queue[n], front = 0, rear = 0;
    int count = 0;

    // 入度为0的顶点入队
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue[rear++] = i;
    }

    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u); // 输出拓扑序列
        count++;

        for (int v = 0; v < n; v++) {
            if (adj[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0) queue[rear++] = v;
            }
        }
    }

    if (count != n) {
        printf("图中有环！\n");
        return -1;
    }
    return 0;
}

2. 关键路径：项目最短工期

关键路径是拓扑排序的进阶应用。在一个带权有向无环图中，每条边代表一个活动，权值代表活动所需时间。关键路径就是所有从起点到终点的路径中，总权值最大的那条。

为什么是最大？因为整个项目的工期取决于最慢的那条链路。你想想看，一个项目里，有些活动可以并行，但总有一些活动是必须串行的，这些串行的活动加起来就是关键路径。

计算关键路径需要四个值：事件最早发生时间（ve）、事件最迟发生时间（vl）、活动最早开始时间（e）、活动最迟开始时间（l）。关键活动就是 e == l 的那些活动。

// 计算关键路径的伪代码思路
// 1. 拓扑排序，得到序列
// 2. 按拓扑序计算 ve（最早发生时间）
// 3. 按逆拓扑序计算 vl（最迟发生时间）
// 4. 遍历每条边，计算 e 和 l，找出关键活动

这个算法在项目管理、工程排期中非常实用。我记得有一次帮一个朋友做施工进度优化，用关键路径法找出了可以压缩工期的几个关键活动，最后帮他们省了将近两周的时间。

四、知识体系总览

说了这么多，我画了一张图，帮你把这一讲的知识结构理清楚。

好了，这一讲的内容就到这里。图的内容确实不少，但只要你把 Prim、Kruskal、Dijkstra、Floyd、拓扑排序、关键路径这几个算法吃透，面试和工程中的图问题基本都能应对。下一讲我们会进入一个全新的领域——查找与排序的进阶话题。

---

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