图的深度优先遍历（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²)。

七、加强记忆

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

简化版

详细版