图搜索

🗺️ BFS vs DFS

图搜索是解决路径、连通性问题的核心算法。

🗺️图搜索 BFS vs DFS

BFS 广度优先搜索使用队列，层层扩展

时间 O(V+E)空间 O(V)

速度:

起点 (S)

终点 (E)

墙 (点击绘制)

访问中

已访问

最终路径

🌊 BFS 特点

• 使用队列 (FIFO)
• 层层扩展，先近后远
• 保证最短路径 (无权图)
• 适合: 最短路径、层序遍历

🏃 DFS 特点

• 使用栈 (LIFO) / 递归
• 一条路走到底，回溯
• 不保证最短
• 适合: 连通性、拓扑排序、回溯

🎯 核心对比

特性	BFS (广度优先)	DFS (深度优先)
数据结构	队列 (FIFO)	栈 (LIFO) / 递归
搜索策略	层层扩展	一条路走到底
最短路径	✅ 保证 (无权图)	❌ 不保证
空间复杂度	O(V) 较大	O(V) 较小
适用场景	最短路径、层序	连通性、拓扑排序

📝 代码实现

BFS (广度优先)

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // 从队首取出
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // 加入队尾
      }
    }
  }
}

DFS (深度优先)

// 递归版
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);

  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

// 迭代版
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop(); // 从栈顶取出
    if (visited.has(node)) continue;

    visited.add(node);
    console.log(node);

    for (const neighbor of graph[node]) {
      stack.push(neighbor);
    }
  }
}

📊 复杂度分析

对于图 G = (V, E)：

V = 顶点数
E = 边数

算法	时间	空间
BFS	O(V + E)	O(V)
DFS	O(V + E)	O(V)

🎯 经典应用

BFS 适用

最短路径 (无权图)
层序遍历
多源 BFS
拓扑排序 (Kahn 算法)

DFS 适用

连通分量
环检测
拓扑排序 (后序)
回溯算法
迷宫生成

🔗 相关知识

栈与队列 - BFS/DFS 的核心数据结构
二叉树 - 树是特殊的图
动态规划 - 图上的最优化问题