数据配置

连通性查询

算法状态

当前连通分量 0
已访问节点 0
当前递归深度 0
最大递归深度 0
连通分量颜色

网格可视化

墙壁
通路
访问中
深层递归
=======

点击格子切换墙壁/通路状态

递归深度说明
• 数字 = 连通分量编号
• D1, D2, D3... = DFS递归深度
• 颜色越浅 = 递归层次越深
• 边框越粗 = 递归深度越大

算法执行步骤

点击"开始DFS算法"查看执行步骤

算法原理详解

DFS连通分量算法

核心思想：使用深度优先搜索遍历图中的每个连通区域，为每个连通分量分配唯一编号。

时间复杂度：O(n×m)，其中n为行数，m为列数

空间复杂度：O(n×m)，用于存储访问状态

算法步骤

  1. 读取网格，'*'表示可通过，'.'表示墙壁
  2. 遍历每个未访问的'*'格子
  3. 对每个新的连通分量执行DFS
  4. 标记所有连通的格子为同一编号
  5. 回答查询：两点是否属于同一连通分量