BFS 与 DFS:工作表怎样改变探索顺序?
同一张无向图、同一邻接顺序。逐步比较队列头与栈顶如何决定下一节点。
同一张图,队列和栈怎样改变探索顺序?
运行 BFS,先找取出端,再看新邻居去哪里。
当前处理 已发现 / 待处理 已处理
队列(左侧是队头)
已输出顺序
尚未处理
当前步骤
进度—
取出节点—
本轮新发现—
访问集合—
点击“下一步”,观察工作表的取出端。
结论与可信度检查
边界:访问顺序依赖固定邻接顺序;BFS 的无权最短层次保证不依赖同层内部顺序,DFS 也不保证最短路径。
同一轮次,比较工作表
固定同一图、同一邻接顺序;队列从左取,栈从右取。下列记录来自两种真实遍历的相同轮次。