BFS vs DFS

核心区别

维度	BFS（广度优先搜索）	DFS（深度优先搜索）
遍历方式	按层级扩散（一层一层）	沿路径深入到底再回溯
实现数据结构	队列（Queue）	栈（递归调用栈/显式栈）
最短路径	✅ 适合（首次到达即最短）	❌ 不适合（穷举所有路径）
空间复杂度	O(w)（w为最大宽度）	O(h)（h为树高/图深度）
适用场景	最短路径、层序遍历、连通分量	穷举所有路径、拓扑排序、回溯算法

详细对比

算法思想

• BFS：从起点开始，先访问所有距离为1的节点，再访问距离为2的节点，依此类推
• DFS：从起点开始，沿一条路径走到尽头，再回溯到上一个分叉点，继续走下一条路径

代码框架对比

// BFS 框架（用队列）
void bfs(Graph graph, Node start) {
    Queue<Node> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    queue.offer(start);
    visited[start.id] = true;
    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        // 处理当前节点
        for (Node neighbor : graph.getNeighbors(curr)) {
            if (!visited[neighbor.id]) {
                visited[neighbor.id] = true;
                queue.offer(neighbor);
            }
        }
    }
}

// DFS 框架（递归）
void dfs(Graph graph, Node curr, boolean[] visited) {
    visited[curr.id] = true;
    // 处理当前节点
    for (Node neighbor : graph.getNeighbors(curr)) {
        if (!visited[neighbor.id]) {
            dfs(graph, neighbor, visited);
        }
    }
}

应用场景对比

场景	BFS	DFS
二叉树层序遍历	✅	❌
最短路径（无权图）	✅	❌
二叉树前中后序遍历	❌	✅
拓扑排序	❌	✅
连通分量计数	✅	✅
回溯算法（全排列、组合）	❌	✅

相关概念

• BFS：BFS详细概念页
• DFS：DFS详细概念页
• 图：遍历对象