参考文献：图论
定义
- 基本定义：图、阶、有向图、无向图、重边、自环。
- 相邻：相邻、邻域、邻边、出入边、度数，出入度
- 路径：途径、迹、回路、路径、环
- 联通：联通、强弱联通、强弱连通图、点双，边双
- 特殊图：简单图、基图、有向无环图、完全图、树、稀疏稠密图
- 子图：子图、生成子图、导出子图，极大子图
DAG
topo sort
比较简单，每次删去一个没有入度的点，同时删去和这个点联通的边，然后再观察图中有没有没有入度的点就好了。
能被 \(topo \ sort\) 的图，被叫为 \(DAG\)。但有的时候一张图的 \(topo\) 序不止一个，叫做偏序。
欧拉路径/欧拉回路
判定
判定欧拉回路：有向图的话入度都要等于出度，无向图的话是度数要是偶数。
判定欧拉路径：有向图的话除了起始点入度比出度少一，终点的入度比出度多一，无向图是只有起始点和终点的度数是奇数，剩下的是偶数。
所有前提条件都是要图联通！！
求解
直接 \(dfs\) ：对于有向图，对于一个点，如果这个点有出度，随便找到一个出边，先走过去，然后删掉这条边。对于无向图而言，直接随机选择一条边，走过去删掉即可。
两个的 \(dfs\) 都可以用类网络流的当前弧优化！！
特殊题型
混合图的欧拉路径
可以先给无向边定向，然后再跑欧拉路径，但是这样枚举的时间复杂太大了，不能手动给每一条边定向。
观察本质，对吼定向完之后应该是每一个点的出度要等于入度，只有起点和终点一个少了一个入度，一个多了一个入度，如果把度比作流把入度比作流入，把出度比作流出，这就是经典的最大流，直接跑就好了。
最短路
Bellman-Ford
松弛 \(n\) 轮，每轮把 \(m\) 条边松弛一边，可以证明，这样子松弛完之后就是最短路，时间复杂度 \(O(nm)\)。
以下是证明：
松弛的本质是一个点的最短路由另一个点的最短路扩展而来，一轮松弛可以更新一个点的最短路，两点之间的最短路一定最多只有 \(n-1\) 条边，所以更新 \(O(n)\) 轮就可以得到最短路。
SPFA
用队列优化 \(Bellman-Ford\) 的松弛过程，每次松弛最劣的最短路，理想时间复杂度是 \(O(n)\) ，但实际上极易被卡，会退化成 \(O(nm)\)，所以很多选手都不会被使用。
这个算法的优点是可以用来判负环。
dijkstra
这个就不用说了，时间复杂度是 \(O(mlogm)\) 的，当稀疏图时，用优先队列优化，当是稠密图时，用暴力替代优先队列，时间复杂度变为 \(O(m)\)。
优化
当只有 \(01\) 边权的时候，可以把优先队列改成双端队列，如果松弛完之后是 \(0\) 就放队首，\(1\) 放队尾，可以优化掉优先队列的一只 \(log\)。
floyd
本质上是 \(dp\), 其他的最短路基本上本质都是贪心，这是他们之间比较大的区别。
时间复杂度 \(O(n^3)\) ，没人不会吧，由于他的 \(dp\) 特性，它可以求一些其他的特殊最短路问题
传递闭包
这跟 \(floyd\) 的 \(dp\) 特性没有一点关系，他是直接基于 \(floyd\) 加上 \(bitset\) 优化的，用于求两点之间的连通性，这个可以用 \(bitset\) 优化一下，时间复杂度就变成了 \(O(\frac{n^3}{w})\)。在赛场上这个 \(w = 8\) 有着关键的常数作用。