图的存储
- 啥？邻接表和链式前向星不是一个东西吗。。。
拓扑排序
- DFS求拓扑序似乎不太常见？了解就行。
欧拉路
- 这些什么路径的定义确实挺难和名字对上号。。。但是正规题目应该都会给解释吧。
- 欧拉路：从图中某个点出发，遍历整个图，图中每条边通过且只通过一次。
- 欧拉回路：起点和终点相同的欧拉路。
- 数据范围太大 DFS 会爆栈，需要用栈模拟递归。
无向图的连通性 & 有向图的连通性
- 割点割边还有连通分量什么的求法可以现推。
- Kosaraju 算法：可以 \(O(n+m)\) 找到每个 SCC。对于一个有向图 \(G\)，建反图 \(rG\)，从 \(G\) 上每个没有被 DFS 到的点开始 DFS，按回溯顺序从小到大编号，然后在 \(rG\) 上按编号从大到小开始 DFS，每次 DFS 即找到一个 SCC。
基环树
- 看到每个点连一条边的题想到基环树（森林）
- 找无向图基环树的环可以用类似拓扑排序的 BFS，每次找度数为 \(1\) 的。