有向图/无向图的基本操作
有向图 Directed:
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 就好了。 类似于“剥洋葱”，从最外面一层出发，逐步向里。
Count # of connected components
Determine if A is reachable from B
这个任务最适合用 BFS 做，从 B 做起点一路扫看看能不能扫到 A 就行了。
Un-directed:
无向图算法的整体思路和有向图基本一致，但是需要重点注意 正确处理 “原路返回” 的情况，免得死循环或者误报。
在无向图的2个状态基础上增加一个 “正在访问” 的新状态，加上注意 prev 就可以了。
DFS:
Detect Cycle (Graph Valid Tree)
用 int[] 表示每个点的状态，其中 0 代表“未访问”； 1 代表“访问中”； 2 代表“已访问”； DFS call 里要传入 "prev节点" 参数，避免出现原路返回，或者回到前一个节点误判为有环。(和 directed graph DFS 唯一的不同之处)
其他情况下，如果我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。
Topological Sort
都无向图了，topological 个毛
Count # of connected components (Graph Valid Tree)
Determine if A is reachable from B
BFS：
Detect Cycle (Graph Valid Tree)
扫描所有 edges 记录图到底长啥样； 用 "0,1,2" states; 随便扔一个点进 queue，标记 "1"，然后 BFS，所有 child = "0" 的都加入队列 所有 child 都检查完之后，立刻把当前 node = 2，不然下一层 BFS 会回头去看自己然后误报。
如果遇到 child = "1" 的说明有环
Topological Sort
都无向图了，topological 个毛
Count # of connected components (Graph Valid Tree)
和 Detect Cycle 一样，同时记录下到底做了几次 BFS 才扫遍全图，图上就有几个 connected components Determine if A is reachable from B
BFS 搜到底看看能不能到就可以了，这个和只靠 g(x) 的 uniform-cost search 一致。