图的深度优先遍历（DFS）和广度优先遍历（BFS）有什么区别？

简化版

DFS（深度优先）：一条路走到底再回溯，用递归或栈实现，像走迷宫「不撞南墙不回头」。BFS（广度优先）：一层一层向外扩展，用队列实现，像水波纹扩散。两者都用一个 visited 集合防止重复访问，时间都是 O(V+E)（邻接表）。关键区别：BFS 能求无权图的最短路径（第一次到达即最短），DFS 适合找连通性、路径存在性、拓扑排序、环检测。

详细版

DFS（栈 / 递归）：

void dfs(int u, boolean[] visited, List<List<Integer>> adj) {
    visited[u] = true;
    // 处理 u
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(v, visited, adj);   // 深入一个邻居到底
    }
}

BFS（队列）：

void bfs(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(start); visited[start] = true;
    while (!q.isEmpty()) {
        int u = q.poll();          // 处理 u
        for (int v : adj.get(u)) {
            if (!visited[v]) { visited[v] = true; q.offer(v); }
        }
    }
}

维度	DFS	BFS
数据结构	栈 / 递归	队列
扩展方式	一路到底再回溯	一层层向外
无权最短路	❌ 不保证	✅ 保证
空间	O(树高/递归深度)	O(最宽一层)
典型用途	连通性、路径、拓扑、环检测、回溯	无权最短路、层序、扩散

完整版教学

一、visited 是图遍历的命根子

图和树遍历最大的不同：图可能有环、可能有多条路径到同一个点。如果不做标记，会无限循环或重复访问。所以图的 DFS/BFS 都必须有一个 visited 集合/数组，访问过的点不再进入。这是图遍历区别于树遍历的关键——树没有环，不需要 visited。

二、DFS：栈驱动的「一条道走到黑」

DFS 从起点出发，选一个邻居深入，再从那个邻居继续深入……一直到没有未访问的邻居，才回溯到上一个岔路口换方向。它天然用栈（递归就是借助系统调用栈）。特点是沿着一条路径尽可能深入。适合：

判断连通性 / 路径是否存在：能不能从 A 走到 B。
拓扑排序（后序逆序）、环检测（三色标记）。
回溯类问题：全排列、组合、迷宫所有路径——本质是带撤销的 DFS。

注意深图递归可能栈溢出，可改用显式栈迭代。

三、BFS：队列驱动的「层层扩散」

BFS 从起点出发，先访问所有直接邻居（第 1 层），再访问邻居的邻居（第 2 层）……像水波纹一圈圈扩散。它用队列（先进先出保证按层推进）。核心特点是按距起点的距离分层推进，这带来一个关键能力：

四、为什么 BFS 能求无权最短路

在无权图里，BFS 第一次到达某个顶点时，走过的边数一定是最少的——因为 BFS 严格按层扩展，第 k 层的点距起点恰好 k 步。所以「第一次访问到目标 = 最短路径」。这是 BFS 最重要的应用：无权图/网格图的最短路径、最少步数问题（如迷宫最短路、单词接龙）。

注意：带权图的最短路 BFS 不行（每条边权重不同，边数少不等于距离短），要用 Dijkstra 等。BFS 的最短路只对「每条边权重相同」成立。

五、复杂度与选择

时间：都是 O(V + E)（每个顶点、每条边各处理一次，邻接表）。邻接矩阵是 O(V²)。
空间：DFS 是 O(递归深度)（最坏 O(V)）；BFS 是 O(最宽一层)（最坏 O(V)）。
怎么选：求最短路/最少步数（无权）用 BFS；找路径存在性、所有路径、拓扑、环、回溯用 DFS。

六、常见误区与追问

考点	正确口径
DFS	栈/递归，适合路径探索和回溯
BFS	队列，适合按层扩展和无权最短路
共同点	图遍历都必须处理 visited

DFS: push deeper before siblings
BFS: process all distance d nodes before distance d+1
visited prevents repeated cycles

图遍历和树遍历最大的差别是：图可能有环，所以 visited 是命根子。

误区：图 DFS 不需要 visited。 有环图会无限递归或重复访问，必须记录访问状态。
误区：BFS 能求所有带权图最短路。 BFS 只保证无权图或等权图的最短边数，带权图需要 Dijkstra 等算法。
误区：DFS 一定比 BFS 省空间。 DFS 空间与递归深度有关，BFS 与层宽有关，具体取决于图结构。
追问：为什么 BFS 能求无权最短路？ 它按距离层层推进，第一次到达某点时经过的边数最少。
追问：DFS 更适合什么？ 连通性、拓扑排序、环检测、回溯路径、Tarjan 等依赖深度探索的问题。
追问：复杂度是多少？ 邻接表下二者都是 O(V+E)，邻接矩阵下遍历邻居可能到 O(V²)。

八、一步步推演与边界

回答图的深度优先遍历（DFS）和广度优先遍历（BFS）有什么区别？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

补充边界演练

为了把图的深度优先遍历（DFS）和广度优先遍历（BFS）有什么区别？真正讲透，可以再补一组边界演练。第一组是空结构或空输入，用来确认代码不会在访问 head、root、stack top 或队首时崩溃；第二组是单元素，用来确认循环条件不会多走一步；第三组是 2～3 个元素的最小非平凡样例，用来观察指针、栈、队列或 visited 状态如何变化。

如果是树遍历题，就画出 root、left、right 三个节点，逐步记录栈里元素的进出；如果是图遍历题，就用 4 个点、4 条边验证 BFS 的层次性和 DFS 的路径性；如果是链表题，就把 pre、cur、next 三个指针写在纸上，每移动一次都检查链是否断开。面试时把这个过程讲出来，比单纯写出最终代码更能说明你真的理解结构变化。

边界 1：空输入 -> 直接返回，不访问节点属性
边界 2：单元素 -> 循环最多处理 1 次，结果保持合法
边界 3：三个元素 -> 手动跟踪每一步状态变化
验证目标：不变量始终成立，且每个节点/元素被处理次数可解释

七、加强记忆

图遍历都要 visited 防重复（因为图有环）。DFS：栈/递归，一路到底再回溯，用于连通性、路径、拓扑、环检测、回溯。BFS：队列，一层层扩散，能求无权图最短路（第一次到达即最短，因按层推进）。两者时间都 O(V+E)。带权图最短路不能用 BFS（要用 Dijkstra）。口诀:无权最短路用 BFS，其余探索用 DFS。

简化版

详细版