BFS与DFS图遍历可视化

广度优先 vs 深度优先搜索

BFS（广度优先搜索）和DFS（深度优先搜索）是两种基本的图遍历算法。BFS使用队列，逐层扩展；DFS使用栈（或递归），尽可能深入探索。

BFS (队列)
队列
访问顺序
选择模式后点击开始

BFS vs DFS 对比

特性 BFS DFS
数据结构 队列 (FIFO) 栈 (LIFO) / 递归
访问顺序 逐层扩展（由近及远） 尽可能深入，再回溯
最短路径 保证找到（无权图） 不保证
空间消耗 可能较大（存储整层） 通常较小

时间与空间复杂度

指标 BFS DFS
时间复杂度 O(V + E) O(V + E)
空间复杂度 O(V) O(V)

V是顶点数，E是边数。两种算法时间复杂度相同，但实际空间使用取决于图的结构。

应用场景

BFS适用于：

  • 无权图的最短路径
  • 社交网络中的"六度分隔"
  • 迷宫的最短路径
  • 网页爬虫

DFS适用于：

  • 拓扑排序
  • 检测图中的环
  • 寻找连通分量
  • 解决迷宫问题（所有路径）
  • 回溯算法
最短路径 拓扑排序 连通性检测 迷宫求解

代码实现

from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order


def dfs(graph, start, visited=None):
    """深度优先搜索（递归）"""
    if visited is None:
        visited = set()
    
    visited.add(start)
    order = [start]
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    
    return order


# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'], 'E': ['B'], 'F': ['C']
}
print("BFS:", bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
print("DFS:", dfs(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']
import java.util.*;

public class BfsDfs {
    
    /**
     * 广度优先搜索
     */
    public static List<String> bfs(
            Map<String, List<String>> graph, 
            String start) {
        
        List<String> order = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            String node = queue.poll();
            order.add(node);
            
            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return order;
    }
    
    /**
     * 深度优先搜索
     */
    public static void dfs(
            Map<String, List<String>> graph,
            String node,
            Set<String> visited,
            List<String> order) {
        
        visited.add(node);
        order.add(node);
        
        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, order);
            }
        }
    }
}