图算法：从遍历到最短路

第一次碰到“图算法：从遍历到最短路”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：我最初看到图题就先写 DFS，后来才意识到边有没有权、是否存在环、要不要最短路径，会直接改变整个解法。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

图算法是数据结构与算法里最接近真实世界的一块。课程依赖、城市道路、服务调用、社交关系、转账网络、知识图谱，本质上都可以看成点和边。

学图算法之前，必须先把图建模讲清楚。边有没有方向？有没有权重？是否允许负权？图是稀疏还是稠密？问题是可达性、最短路、依赖排序，还是生成树？这些都会改变算法选择。

图算法选择路线

图：图算法先根据问题类型选择路线

问题	条件	常见算法
是否可达	不关心权重	BFS / DFS
最少边数路径	无权图	BFS
依赖顺序	有向无环图	拓扑排序
单源最短路	非负权	Dijkstra
单源最短路	可有负权	Bellman-Ford
多源最短路	点数较少	Floyd
最小连接成本	无向连通加权图	Prim / Kruskal
动态连通	主要合并集合	并查集

BFS：按层扩散

BFS 使用队列，适合找无权图的最少边数路径。

List<Integer> bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : graph.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.offer(v);
            }
        }
    }
    return order;
}

注意：通常在入队时标记 visited，而不是出队时再标记。否则同一个节点可能被多个前驱重复加入队列。

DFS：沿路径深入

DFS 可以用递归，也可以用栈。它适合连通分量、环检测、拓扑排序和路径枚举。

void dfs(List<List<Integer>> graph, int u, boolean[] visited) {
    visited[u] = true;
    for (int v : graph.get(u)) {
        if (!visited[v]) {
            dfs(graph, v, visited);
        }
    }
}

工程里如果图很深，递归 DFS 可能栈溢出，可以改成显式栈。

拓扑排序

拓扑排序用于有向无环图。比如课程先修关系、任务依赖、构建流程。

Kahn 算法使用入度：

List<Integer> topoSort(int n, List<List<Integer>> graph) {
    int[] indegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) indegree[v]++;
    }
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.offer(i);
    }
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : graph.get(u)) {
            if (--indegree[v] == 0) q.offer(v);
        }
    }
    if (order.size() != n) throw new IllegalStateException("graph has cycle");
    return order;
}

如果最后结果数量小于节点数，说明图里有环，不能得到合法拓扑序。

Dijkstra：非负权最短路

Dijkstra 适合边权非负的单源最短路。它每次取当前距离最小的点，并用它去松弛邻居。

int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{start, 0});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d != dist[u]) continue;
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

Dijkstra 不能直接处理负权边，因为“当前最短点已经确定”这个前提会被负权破坏。

Bellman-Ford 和 Floyd

Bellman-Ford 可以处理负权边，并能检测负环。它的思想是反复松弛所有边，最多做 V-1 轮。如果第 V 轮还能继续变短，说明存在负环。

Floyd 用动态规划求任意两点之间最短路，复杂度 O(V³)，适合点数较少的场景。

最小生成树

最小生成树解决的是：在无向连通加权图中，用最小总权重连接所有点。

常见算法：

Prim：从一个点开始，不断选择连接当前集合和外部集合的最小边。
Kruskal：把所有边按权重排序，从小到大选择不会形成环的边，通常配合并查集。

最短路和最小生成树不要混淆。最短路关注从源点到某点路径最短；最小生成树关注连接全部点的总成本最小。

常见错误

没有明确图是有向还是无向。
无向图只加了一条边。
BFS 出队时才标记 visited，导致重复入队。
拓扑排序没检查是否有环。
Dijkstra 用在负权图上。
最短路权重含义和业务含义不一致。
大图递归 DFS 栈溢出。

工程场景

课程学习路径：拓扑排序。
地图导航：最短路。
服务依赖分析：DFS、拓扑排序、环检测。
社交关系推荐：BFS、多跳邻居。
网络建设成本：最小生成树。
权限继承：有向图可达性。
知识图谱：带类型的关系图。

工程里的图经常不是静态的。边可能有时间、权重、类型、权限和版本。算法写对只是第一步，建模错了结果一样会错。

面试题

BFS 为什么能求无权图最短路径？
DFS 如何检测有向图环？
拓扑排序为什么只能用于 DAG？
Dijkstra 为什么不能处理负权边？
Prim 和 Kruskal 的区别是什么？
最短路和最小生成树有什么区别？

小结

图算法不是从背名字开始，而是从问题建模开始。先判断点和边的语义，再判断问题目标，最后选择算法。可达用 BFS/DFS，依赖用拓扑排序，非负最短路用 Dijkstra，负权考虑 Bellman-Ford，多源小图用 Floyd，连接成本用最小生成树。