图与图的遍历：BFS、DFS 与拓扑排序

前面讲的都是”线性”（数组、链表）和”层次”（树）结构。但现实中有大量关系是”网状”的：

社交网络里，谁关注谁
城市之间，怎么导航
项目里，任务之间的依赖

这些用树表达不了，因为树不允许”环”，而现实关系到处是环。这时候就需要图。

图的基本概念

图由**顶点（Vertex）和边（Edge）**组成。

按边的方向，分为：

无向图：边没有方向（如”互为好友”）
有向图：边有方向（如”A 关注了 B”，单向）

按边是否带权重，分为：

无权图：边都一样
带权图：边有权重（如”两个城市之间的距离”）

图的两种存储方式

1. 邻接矩阵

用一个二维数组 matrix[i][j] 表示”从 i 到 j 是否有边”。

优点：判断”i 和 j 是否有边”是 O(1)，简单直观
缺点：空间 O(n²)，稀疏图（边很少）会浪费大量空间

2. 邻接表

每个顶点维护一个”它指向的邻居”列表。

优点：空间 O(V + E)，稀疏图很省
缺点：判断”i 和 j 是否有边”要遍历 i 的邻居列表，O(度数)

工程上邻接表更常用，因为现实中的图大多是稀疏的。

广度优先遍历（BFS）

BFS 按”层”逐层向外扩展，像水波纹一样。

它用队列实现：

void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visit(node);
        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

BFS 的核心应用：求无权图的最短路径。因为它是逐层扩散的，第一次到达某个节点时，走的就是最短的层数。

深度优先遍历（DFS）

DFS 沿着一条路走到底，走不通再回溯。

它用递归（或显式栈）实现：

void dfs(Node node, Set<Node> visited) {
    visited.add(node);
    visit(node);
    for (Node neighbor : node.neighbors) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

DFS 的核心应用：连通性判断、找环、拓扑排序、回溯（后面会专门讲回溯）。

BFS vs DFS 怎么选

场景	选择
求最短路径（无权图）	BFS
遍历所有连通分量	都可以
找是否存在环	DFS
拓扑排序	DFS 或 BFS（Kahn 算法）
迷宫找路径	BFS（最短）/ DFS（找一条即可）

一个记忆技巧：BFS 关注”距离”，DFS 关注”深度”。

拓扑排序

拓扑排序解决的是”有依赖关系的一堆任务，应该按什么顺序执行“。

典型场景：编译依赖、课程表安排、任务调度。

它只适用于有向无环图（DAG）——如果图里有环，就说明存在循环依赖，无法拓扑排序。

思路（Kahn 算法，基于 BFS）：

统计每个节点的入度（有多少个节点指向它）
把所有入度为 0 的节点加入队列
出队一个节点，把它指向的所有邻居的入度减 1，减到 0 的加入队列
重复直到队列为空

如果最后排序出的节点数 < 总节点数，说明图里有环。

图的经典问题

掌握了图的遍历，就打开了通往这些经典算法的大门：

最短路径：Dijkstra（带权）、Floyd（多源）
最小生成树：Kruskal、Prim
连通性：并查集

这些先不做深入，但它们都以 BFS/DFS 为基础。

写在最后

图是数据结构里最灵活、也最贴近真实世界的一种。学图的重点不是背代码，而是学会把现实问题”建模”成图：

一旦你把问题抽象成”节点 + 边”，就能用 BFS/DFS 这套成熟的工具去解决它。

下一篇讲排序算法——一个几乎所有面试都会涉及的话题。