图论算法概述
liweiwei1419 ... 2021-12-15 About 1 min
# 参考资料
- 《算法(第 4 版)》
- 《算法导论》
# 「最短路径问题」知识点
「最短路径问题」专题要解决的问题和重点:
- 单源最短路径问题(Dijkstra 算法、Bellman-Ford 算法)
- 所有点对的最短路径问题(Floyd 算法)。
提示
本专栏只讲解 Dijkstra 算法和「松弛操作」。
# 单源最短路径问题
- Dijkstra 算法(没有负权边的单源最短路径问题,重点讲解)
- 松弛操作:重点强调由于没有负权边,因此每一轮可以确定从源点到一个顶点的最短路径
- 算法思想:贪心算法、动态规划
- 数据结构:堆(优先队列)
- 时间复杂度
- Bellman-Ford 算法(有负权边的单源最短路径问题)
- 算法思想:动态规划
- 需要讲清楚进行顶点个数 - 1 次操作是找到最短路径的上限,并且最后还要执行一次松弛操作判断是否有负权环
- SPFA 算法的思想可以提一下,甚至可以不讲,面试肯定不会考
- 时间复杂度
# 所有点对的最短路径问题
Floyd 算法其实还是松弛操作和动态规划。
# 「最小生成树」知识点
「最小生成树」专题要解决的问题:
找到无向图的最小生成树。
# 切分定理
Kruskal 算法和 Prim 算法都利用到了「切分定理」。
# Kruskal 算法
- 算法思想:贪心算法
- 数据结构:并查集
# Prim 算法
- 算法思想:贪心算法
- 数据结构:堆(优先队列)