图论算法概述

参考资料

• 《算法（第 4 版）》
• 《算法导论》

「最短路径问题」知识点

「最短路径问题」专题要解决的问题和重点：

1. 单源最短路径问题（Dijkstra 算法、Bellman-Ford 算法）
2. 所有点对的最短路径问题（Floyd 算法）。

提示

本专栏只讲解 Dijkstra 算法和「松弛操作」。

单源最短路径问题

1. Dijkstra 算法（没有负权边的单源最短路径问题，重点讲解）

• 松弛操作：重点强调由于没有负权边，因此每一轮可以确定从源点到一个顶点的最短路径
• 算法思想：贪心算法、动态规划
• 数据结构：堆（优先队列）
• 时间复杂度

2. Bellman-Ford 算法（有负权边的单源最短路径问题）

• 算法思想：动态规划
• 需要讲清楚进行顶点个数 - 1 次操作是找到最短路径的上限，并且最后还要执行一次松弛操作判断是否有负权环
• SPFA 算法的思想可以提一下，甚至可以不讲，面试肯定不会考
• 时间复杂度

所有点对的最短路径问题

Floyd 算法其实还是松弛操作和动态规划。

「最小生成树」知识点

「最小生成树」专题要解决的问题：

找到无向图的最小生成树。

切分定理

Kruskal 算法和 Prim 算法都利用到了「切分定理」。

Kruskal 算法

• 算法思想：贪心算法
• 数据结构：并查集

Prim 算法

• 算法思想：贪心算法
• 数据结构：堆（优先队列）