1.BFS算法的基础理论是什么?
BFS算法名叫宽度优先搜索,虽然我能理解深度优先搜索,但我却不是很能理解宽度优先搜索。
一个很关键的点在于:宽度优先搜索是一个迭代的算法,不是递归的算法。
与DFS之间的区别:
DFS是利用栈的特性进行搜索的。
而BFS是利用队列的特性进行搜索的,队列的话,不能利用系统的特性,所以使用过程中得创建一个队列。
2.BFS的代码模板
一、不需要区分目前遍历到那一层了:
while(队列非空) { int len = 队列.size(); for(len) //执行len次,将队中所有的值先pop掉 { TreeNode* tmp=队头; pop出; 存储tmp值; 装新值; } } 就是这样一边出一边进。
3.宽度优先搜索需要对很多问题进行抽象,建模
这也造成了宽度优先搜索类的题目或者思路比较难想到。