图论

BFS

腐烂的橘子

• 所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

Q：为什么这题不用DFS用BFS？

A：这道题要求返回直到网格中没有新鲜橘子为止所必须经过的最小分钟数。实际上就是求腐烂橘子到所有新鲜橘子的最短路径。因为BFS可以用来求最短路径问题。BFS先搜索到的结点，一定是距离最近的结点；而DFS会先往深度更深的方向搜索，某些离起点更近的点可能因为上一次深搜回退被搜索，另外，DFS为了保证一个点不被重复搜索，离起点更近的新鲜橘子被绕弯路搜到后，就不会再被从起点出发更近的路径搜索，导致得到的最短路径比真实的最短路径长。

Q：多个起点的BFS如何处理？

A：起始时以每个腐烂橘子作为起点都做一次广度优先搜索的方法过于耗时，一种比较好的方法是多源广度优先搜索。假设起始的腐烂橘子是从一个超级源点扩散而来的，即从超级源点开始做广度优先搜索，刚开始的时间为-1，在时间为0的时候把起始的腐烂橘子变成腐烂句子，然后继续向下一层搜索。

为了确认是否所有新鲜橘子都被腐烂，可以用一个变量cnt表示当前网格中的新鲜橘子个数，也就是可以一边搜索一边判断是否达到目标。（DFS通常不能这么做，可能需要在DFS结束后再检查是否满足目标条件）。

Topological Ordering

Q：判断一个图是否含有topological ordering时候，是否需要创建一个数组记录已经从图中删除过的顶点从而避免重复访问？

A：不需要。用反证法可以证明：假设一个顶点已经被删除了，但它还可能被访问，那么该图还存在指向该顶点的边。由于该顶点之前已经被删除，说明已经不存在指向该顶点的边，与假设矛盾。所以如果一个顶点已经被删除了，之后就不会再被访问了。