Graph

[caipengbo]

• 图的实现
• 图的常见算法
• 图的典型题目

[caipengbo]

DFS

深度优先搜索树

染色来区别状态，未被遍历，被其他搜索树遍历，被当前搜索树遍历

算法导论

[caipengbo]

BFS

[caipengbo]

拓扑排序

判断是否有环

DFS方法的Flag数组以及DFS的具体流程，很重要！！！

[caipengbo]

最短路径

单源最短路径

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

[caipengbo]

并查集

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

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