图

图的表示

• 邻接矩阵
• 邻接表

图的遍历

DFS

• 递归
• 染色（记录、判断状态）：
  1. 直接在图上改变图的值
  2. 开辟一个额外的数组(Flag)记录：未被、访问当前搜索树访问过、其他搜索树访问过（注意判断是否满足访问条件）

BFS

判断联通

Flood BFS DFS

拓扑排序

判断是否有环

最短路径

单源最短路径

• Dijkstra算法（单源，无负权）（朴素、堆优化版）
• Bellman-Ford算法（单源，可以判断负权回路）（队列优化：SPFA）
• Floyd算法（多源，无负权）

最小生成树

Kruskal Prim

并查集

并查集是搞连通性问题的，而连通性问题一般都可以通过DFS，BFS去解决，当然并查集的效率会更高些

并查集本质上就是一个染色的过程