宽度优先搜索BFS

宽度优先搜索BFS

宽度优先搜索BFS

1、学习大纲：

• 二叉树上的宽搜
• 图上的宽搜
• 拓扑排序
• 棋盘上的宽搜

2、什么时候使用BFS?

小问：如果题目问最短路径，除了BFS还可能是什么算法？如果问最长路径呢？
答案：最常见的算法中，BFS还可以用DP；如果是最长路径的话，可以用DFS和DP。

3、基础知识

小点：BFS的标配是队列，DFS的标配是栈。

如果是层级遍历的话，代码实现步骤可以大体分三步：

1. 创建一个队列，把起始点都放到里面去（第一层节点）
2. while队列不空，处理队列中的节点，并扩展出新的节点
3. 在while循环中，for上一层的节点扩展下一层节点

4、代码模板题

题目：Lintcode 69. 二叉树的层次遍历
题目描述：给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）。
（题外话：本题需要层级遍历，如果碰到不需要遍历的问题，最主要的改动是将while里面的for循环去掉就成）

/*** Definition of TreeNode:* class TreeNode {* public:*     int val;*     TreeNode *left, *right;*     TreeNode(int val) {*         this->val = val;*         this->left = this->right = NULL;*     }* }*/class Solution {
public:/*** @param root: A Tree* @return: Level order a list of lists of integer*/vector<vector<int>> levelOrder(TreeNode * root) {vector<vector<int>> result;if (nullptr == root) {return result;}//1、创建队列，将起始点放入queue<TreeNode* > nodeQueue;nodeQueue.push(root);//2、while队列不空，处理队列中节点，并扩展出新节点while (!pty()) {vector<int> levelResult;//3、在while中，for上一层的节点扩展下一层节点int queueSize = nodeQueue.size();for (int i = 0; i < queueSize; ++i) {TreeNode* node = nodeQueue.front();levelResult.push_back(node->val);if (nullptr != node->left) {nodeQueue.push(node->left);}if (nullptr != node->right) {nodeQueue.push(node->right);}nodeQueue.pop();}result.push_back(levelResult);}return result;}
};