应用BFS解题时，有几大关键点需要注意：
1.队列queue(重要)
队列queue是BFS的核心数据结构，记录当前广度遍历到的点。
2.邻接表/邻接矩阵(重要)
邻接关系数据结构泛指curr相邻的节点，比如说二维数组中，curr上下左右的位置就是相邻节点；或者，换一种理解，记录一个点可以通到的地方，即两个点之间的关系。
节点和边——数据之间的关系
3.访问记录列表visited(重要)
visited的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。
4.先驱、后驱(可选，记录路径)
先驱、后驱用于记录当前节点的前一个节点、后一个节点。
5.步数(可选，记录距离)
步数，是在遍历到每一层时，记录的step数，当前层遍历完后，step++，用于记录当前节点的距离。
附：
DFS/BFS定式
yo peace！
BFS例题---走迷宫 BFS对应数据结构queue BFS算法时间复杂度O(n^2) BFS算法不走走过的点 的...
参考什么时候用dfs，什么时候用bfs 参考什么时候用DFS，什么时候用BFS? BFS的缺点适用情况 BFS的一...
BFS vs DFS for Binary Tree What are BFS and DFS for Binar...
BFS BFS在搜索完第k层的节点之前，是不会搜索第k+1层的节点的。 BFS原理 BFS所用的是队列。把每个还没...
1. 题目列表 POJ3126（BFS） POJ3087（BFS） POJ3414（BFS+路径打印） 2. 广搜...
内容概要： BFS类的实现 BFS求解连通分量 BFS求解无向图点对之间的一条最短路径 BFS判定无环图和二分图 ...
317 . Shortest Distance from All Buildings 典型的BFS的题目，BFS可...
BFS
BFS判断连通性 DFS判断连通性 BFS最优解(不走重复路径) BFS最优解(走重复路径) DFS回溯(不走重复...
BFS BFS基于队列，层层遍历每个节点只访问了一次，时间复杂度O(N) 关于Tree的BFS：首先root节点入...
本文标题：BFS定式
本文链接：https://www.haomeiwen.com/subject/rlypgdtx.html
网友评论