You need to enable JavaScript to run this app. 邻接矩阵下的BFS遍历顺序是什么?附DFS遍历实现代码示例
优惠活动
大模型
产品
解决方案
定价
更多

邻接矩阵下的BFS遍历顺序是什么?附DFS遍历实现代码示例

邻接矩阵存储结构下的BFS遍历规则

基础实现约定

所有规则和你给出的DFS实现基准完全对齐:

  • 采用给定的5x5邻接矩阵int[][] grid = new int[5][5]作为存储结构
  • 坐标约定为grid[y][x],其中y为行索引、x为列索引,合法索引范围为0≤y≤4、0≤x≤4;邻接节点为上下左右四个直连方向,不考虑斜向邻接,访问邻接点前必须做边界判定,避免数组越界。

核心运行逻辑

邻接矩阵下的BFS基于先进先出(FIFO)队列实现逐层扩散,和DFS基于栈的后进先出(LIFO)逻辑有本质区别,完整执行流程为:

  1. 从选定的起始节点出发,将该节点标记为已访问,把坐标存入队列尾部
  2. 循环执行出队操作:从队列头部取出一个节点坐标,按预先定义的固定方向顺序逐一检查该节点的四个直连邻接点
  3. 对每个检查到的邻接点,如果坐标合法且未被访问过,立即将其标记为已访问,按检查的先后顺序存入队列尾部
  4. 重复以上出队、邻接点检查、入队的流程,直到队列为空,完成全图遍历

匹配给定DFS方向体系的固定遍历顺序

由于BFS队列的先进先出特性,邻接点的检查入队顺序就是实际遍历的先后顺序,不会出现栈结构下入队和弹出顺序颠倒的问题。对应你给出的两套DFS方向规则的BFS遍历顺序如下:

对应递归DFS方向的BFS顺序

你给出的递归DFS的邻接点检查顺序为「下→上→右→左」,如果BFS沿用完全一致的邻接点检查逻辑,邻接点的入队(遍历优先级)顺序为:

  • 优先检查下方邻接点:坐标grid[y+1][x],合法且未访问则入队
  • 其次检查上方邻接点:坐标grid[y-1][x],合法且未访问则入队
  • 再检查右方邻接点:坐标grid[y][x+1],合法且未访问则入队
  • 最后检查左方邻接点:坐标grid[y][x-1],合法且未访问则入队
    这个顺序下,BFS会严格按照到起始节点的步长距离逐层遍历:先遍历所有距离1步的邻接点,再遍历所有距离2步的节点,不会像DFS那样沿着单条路径走到网格边界再回溯。

对应迭代DFS栈操作顺序的BFS顺序

你给出的迭代DFS的邻接点压栈顺序为「左→右→上→下」,由于栈是后进先出,这个压栈顺序实际弹出的顺序刚好匹配上述递归DFS的遍历顺序。如果BFS沿用完全一致的邻接点入队逻辑,邻接点的入队(遍历优先级)顺序为:

  • 优先检查左方邻接点:坐标(y, x-1),合法且未访问则入队
  • 其次检查右方邻接点:坐标(y, x+1),合法且未访问则入队
  • 再检查上方邻接点:坐标(y-1, x),合法且未访问则入队
  • 最后检查下方邻接点:坐标(y+1, x),合法且未访问则入队

注意:因为BFS队列是先进先出,这个入队顺序下实际遍历邻接点的先后就是入队顺序,和同方向入栈的迭代DFS的弹出遍历顺序完全不同。例如从网格左上角(0,0)出发,这个顺序下第一个入队的有效邻接点是右方的(0,1),后续会先处理这个点,再处理下方的(1,0),和递归DFS先处理下邻接点的顺序相反。

邻接矩阵下BFS和DFS的核心差异

  • 数据结构逻辑差异:DFS不管是递归依赖的系统调用栈,还是迭代使用的手动栈,均为后进先出逻辑,邻接点的入栈顺序和实际遍历顺序相反;BFS使用的队列为先进先出逻辑,邻接点的入队顺序和实际遍历顺序完全一致。
  • 遍历扩散逻辑差异:DFS沿单条路径深度优先,走到路径尽头后再回溯遍历其他分支;BFS按到起始节点的距离分层,逐层向外扩散,同一步长距离的节点全部遍历完成后,才会进入下一层的遍历。

内容的提问来源于stack exchange,提问作者user3587180

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.19 20:06:07