迷宫生成与路径搜索可视化

迷宫配置与控制

20%
状态: 请生成迷宫 | 访问: 0 | 长度: 0
墙 路 起 终 访问中 已访问 回溯 最终路径

C++ 示例代码

深度优先搜索 (DFS) 原理

DFS 优先探索一条路径直到尽头，遇到死路再回溯到上一个路口，选择下一个可行的方向继续探索。常使用栈 (Stack) 来辅助实现。

特点:

  • 不一定找到最短路径。
  • 空间复杂度相对较低（最坏情况是路径深度）。
  • 容易产生非常深的递归（如果用递归实现）。

迭代步骤:

  • 起点入栈，标记已访问。
  • 当栈不空：弹出节点 `curr`。
  • 若 `curr` 是终点，则找到路径，回溯构造。
  • 查找 `curr` 的 *第一个* 未访问邻居 `next`。
  • 若找到 `next`：标记 `next` 已访问，记录父节点，将 `curr` 压回栈（用于回溯），将 `next` 压栈，break (继续深入此路径)。
  • 若未找到 `next`：`curr` 无路可走（死胡同），标记为回溯（可视化）。
  • 若栈最终为空，则说明无解。

广度优先搜索 (BFS) 原理

BFS 像水波纹一样，从起点开始，一层一层地向外扩展搜索。常使用队列 (Queue) 来辅助实现。

特点:

  • 在无权图中，保证找到起点到终点的最短路径。
  • 空间复杂度相对较高（最坏情况可能需要存储所有节点）。
  • 通常用于寻找最短距离或层级遍历。

步骤:

  • 起点入队，标记已访问。
  • 当队列不空：出队节点 `curr`。
  • 若 `curr` 是终点，则找到路径，回溯构造。
  • 查找 `curr` 的 *所有* 未访问邻居 `next`。
  • 对于每一个 `next`：标记已访问，记录父节点，将其入队。
  • 若队列最终为空，则说明无解。