BFS小结

BFS

        通过一些leetcode上面的题目, 总结出以下类型的题目:

树的层序遍历类型。搜索联通块。拓扑排序。最短路径。 无边权重有边权重边界扩展。增广

         BFS 是基于向量的, 一般都需要一个状态数组， 一个增广队列。状态数组是为了防止相同状态的节点再次进后重复加入队列当中。

---

层序遍历

         从根节点开始, 距离的根节点最近的顶点优先遍历。

         因为同一个顶点不存在会被访问两次的情况, 所以不需要状态数组。

模板

queue<TreeNode*> nodes; /* 增广队列。*/ nodes.push(root); /* 压入树的根节点。*/ while(!nodes.empty()) { TreeNode *node = nodes.front(); nodes.pop(); /* 针对该顶点进行操作的代..... */ // 增广 if(node->left) nodes.push(node->left); if(node->right) nodes.push(node->right); }

题目

leetcode 103. 二叉树的锯齿形层次遍历 技巧: 节点状态中包含节点层数即可。leetcode 199. 二叉树的右视图 节点状态中添加层数这一状态, 当当前节点 和 前一个节点的层数不一致时, 将前一个节点的值保存到答案当中, 最后一个顶点单独处理。

---

搜索联通块

         一般为二维矩阵样式的平面图, 在搜索的时候一个顶点可能出现重复进入的情况, 因此需要一个状态数组避免重复进入的情况。

注意事项

         标记已经访问过的时机为 push 进入增广队列的时候, 而不是弹出队列进行处理的时候。这样能避免很多重复点加入队列。

题目

leetcode 130. 被围绕的区域 从边界的O开始BFS, 替换为-, 最后将矩阵当中的 O 替换成 X, 将- 替换成 O;

---

拓扑排序

        看数据结构当中描述的即可。没什么好说的。需要构建一个入度 和 直接链接到的顶点 的数据结构。

题目

leetcode 210. 课程表 II

---

最短路径

无边权重

        无边权重表明边的权重为1, 当BFS过程当中第一次求出了 源 到 目标的距离即可停止搜索得出答案。

有边权重

        此种情况存在重复进入的情况, 只有当重复进入的顶点的距离 源 的距离小于 当前距离时才发生基于此顶点的增广。

leetcode 787. K 站中转内最便宜的航班

---

边界扩展

        将一个联通块儿的边界不断的向外增大，模板如下:

queue<Point> Q; /* Q中初始化放置联通块儿的边界顶点。 */ while(Q.empty()) { int size = Q.size(); while(size--) { Point p = Q.front(); Q.pop(); /* 朝着其他方向得到新的顶点, 该顶点不在联通块儿当中, 并且可以扩展则添加到增广队列当中。 ...... */ } }

题目

leetcode 934 最短的桥

---

增广

        由一个状态出发, 能得到多个状态, 再依次根据这些的状态得到更多的状态, 由此得出最终的答案, 注意已经添加过的状态无序在添加。

题目

leetcode 127.单词接龙leetcode 279.完全平方数

转载于:https://www.cnblogs.com/Geek-Z/p/11356286.html

相关资源：JAVA上百实例源码以及开源项目