DFS, BFS
假设点的数目为v, time complexity都为O(v)
space complexity, BFS worst case为O(v), 但是DFS为O(d), d为树的最大深度
有向图
DFS
Detect Cycle (Course Schedule)
- 暴力解法：DFS + Backtracking，寻找“所有从当前节点的” path，如果试图访问 visited 则有环；缺点是，同一个点会被探索多次，而且要从所有点作为起点保证算法正确性，时间复杂度非常高
- 最优解法是 CLRS 上用三种状态表示每个节点：
"0" 还未访问过;
"1" 代表正在访问；
"2" 代表已经访问过；
DFS 开始时把当前节点设为 "1";
在从任意节点出发的时候，如果我们试图访问一个状态为 "1" 的节点，都说明图上有环。- 当前节点的 DFS 结束时，设为 "2";
- 在找环上，DFS 比起 BFS 最大的优点是"对路径有记忆"，DFS 记得来时的路径和导致环的位置，BFS 却不行。
Topological Sort
- 类似剥洋葱，可以选择任意点开始向里 DFS ，记录path，后面做的其他 DFS path 都放在之前结果的前面。(CLRS有)
- 等价做法是，把每次 DFS 探索中的 path 按照由内向外的顺序添加(单序列反序), 后进行的 DFS 结果放在之前运行完的结果后面(全序列反序)，然后 reverse 就好了，可以改良 ArrayList 添加的时间复杂度。
- 更简单的做法是用 Java 内置的 LinkedList，支持双端操作。
Count # of connected components
Determine if A is reachable from B
BFS
Detect Cycle (Course Schedule)
- 首先，在 DAG 上找环，DFS 要比 BFS 强。
- 其次重点注意，有向图靠 3 个状态 BFS 是不能正确判断是否有环的，要靠 indegree，一个例子是 【0, 1】 和 【1,0】，环在发现之前已经被标注为 state 2 了。
- 扫一遍所有 edge，记录每个节点的 indegree.
- 在有向无环图中，一定会存在至少一个 indegree 为 0 的起点，将所有这样的点加入queue。
- 依次处理queue里的节点，把每次poll出来的节点的 children indegree -1. 减完之后如果 child 的 indegree = 0 了，就也放入队列。
- 如果图真的没有环，可以顺利访问完所有节点，如果还有剩的，说明图中有环，因为环上节点的 indegree 没法归 0.
Topological Sort
- 步骤同上，扫的时候按顺序 append 就好了。
- 步骤同上，扫的时候按顺序 append 就好了。
Count # of connected components
Determine if A is reachable from B
这个任务最适合用 BFS 做，从 B 做起点一路扫看看能不能扫到 A 就行了。
无向图
无向图算法的整体思路和有向图基本一致，但是需要重点注意 正确处理 “原路返回” 的情况，免得死循环或者误报。所以在函数传入时要加上prev参数，避免原路返回。
