> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/summary.md).

# 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