Introduction

Breadth First Search（Queue实现）

1.BFS在graph和Binary Tree中的区别：

graph中的BFS除了Queue还需要HashSet/HashMap--避免重复在undirected graph

经典图中的BFS：P618

经典二叉树上的BFS：LeetCode 102

2.BFS应用：给出一个点，在graph中找到所有点（参数只给一个点）

2.BFS应用：A到B是否可行

2.BFS应用：求图里的最短路径（简单图-无向无权图）

PS：用DFS不是最优，recursion会产生stackoverflow

3.棋盘问题（graph）

能向下走向右走--Dynamic Programming

四个方向都能走--BFS

4.Time Complexity

O(m+n)--m是点数，n是边数

O(2m+2n) 每个点就被访问两次（进入queue,hashset一次，出queue一次），每条边被访问2次。

5.Topological sorting(拓扑排序)--有可能0~多个

有向图-->不能有环-->有可能为0个（有相互依赖）

所以，不是所有的有向图都能够被拓扑排序，因为它中间存在互相依赖的关系，从而无法确定谁先谁后。在有向图中，这种情况被描述为存在环路。因此，一个有向图能被拓扑排序的充要条件就是它是一个有向无环图(DAG：Directed Acyclic Graph)

图的三种表示方式：边表示法，邻接表法，邻接矩阵。用邻接表存储图比较方便寻找入度为0的节点。

BFS解法:能否找到一个有向数列 (Leetcode 207）

在一个有向图中，每次找到一个没有前驱节点的节点（也就是入度为0的节点），然后把它指向其他节点的边都去掉，重复这个过程（BFS），直到所有节点已被找到，或者没有符合条件的节点（如果图中有环存在）。

• 统计所有点的入度(建立入度数组)

• 把所有入度=0的点放入队列

• 从这个队列开始BFS

• 然后开始遍历队列，从graph里遍历其连接的点，每到达一个新节点，将其入度减一，如果此时该点入度为0，则放入队列末尾。

• 直到遍历完队列中所有的值，若此时还有节点的入度不为0，则说明环存在，返回false，反之则返回true

6.在图中设置障碍的路径问题

P611，P598