什么时候需要用宽搜?

  • 图的遍历
  • 层级遍历
  • 由点到面
  • 拓扑排序

最短路径 Shortest Path in Simple Graph

  • 仅限简单图求最短路径(即途中每条变成都是1且没有方向)

二叉树上的宽搜

  • Binary tree 层级遍历:输入root, 输出list of list。宽度优先搜索最重要的数据结构就是queue。思路,将root加入到queue中,然后只要queue不为空,就持续1,将queue中所有的node pop出来(当前层),并将这些node中的左右节点加入到queue
  • Binary tree Serialiaztion:serialize就是层级遍历,deserialize的话其实也要用到queue,先生成个root放到queue中,再将里面的所有node的左右child填满,然后将queue清空,把左右child加入到queue中

拓扑排序

  • 适用于有方向,且没有环的图。主要解决有依赖关系的问题,比方说A依赖B, B依赖C, A依赖C之类的。

步骤

  • 统计每个点的入度(indegree),把入度为0的点拿出来,这些可以作为起始点
  • 从这些拿出来就可以继续放到队列里面,从图里面删掉,然后便利下一层
  • 可以用拓扑排序拍判断有向图是否有环,如果拓扑排序之后和graph的size相同则没有环

延伸:如何判断有向图里面有闭环?只需要将拓扑排序之后的结果与开始给的graphsize做比较就可以了。因为拓扑排序只会将indegree为0的时候塞到结果。但是如果是有闭环,那永远不会为0.

图上的宽搜

  • 和树上的宽度优先搜索的区别在于图中有,所以需要用到hashmap(dic)
  • 如果只使用基本数据结构来表示一个图的话,得用邻接表 http://www.cnblogs.com/ahalei/p/3651334.html
  • GraphValidTree:判断一个图是否是一个树。要遵守两个条件,一个是边的数量为点的数量加一。另外一个条件是,从某个点出发,宽搜之后,得到所有的点(用dic存储防止重复)。这些点的数量为总共点的数量。因为树的话,直接拿到子节点可以,图的话如果想宽搜,那么遍历的时候,需要用邻接表(一个hash,hash中都为array)来存储某一个点相邻的边,这样才可以用queue,和树的宽搜一样,遍历完所有的点。
  • 无向图可以不用queue,用stack也可以,因为主要目的是找到相邻的节点。
  • GraphClone: 能用bfs的尽量不要用dfs,用dfs非递归非常麻烦。图上一般都用bfs

矩阵中的宽度优先搜索

用dfs的劣势有可能深度太深。

  • 坐标变换数组:
1
2
deltaX = [1, 0, 0, -1]
deltaY = [0, 1, -1, 0]

使用坐标变换数组来找四个方向

  • inBound函数: 将使用完坐标变换数组之后,判断变换后的坐标,在棋盘中是否是合法的
  • 一般矩阵会有三重循环,一个是while queue不为空,一个是遍历当前层上的节点并都pop出来,第三个是遍历当前的四周
  • 最短路径,及时遍历完当前层之后将步数加1就可以了。