《算法导论》图相关算法小结
《算法导论》图相关的内容贯穿很多章节，适用条件各异，而且都有证明过程。如果不打算熟记证明，仅仅是应用，遇到具体场景再去回忆适用于哪种算法不太方便。汇总一下便于查阅。
最近又抽空读了一遍《算法导论》，关于图的内容贯穿了多个章节（比如在动态规划一章埋了无权最短路径的伏笔，后面才专门讲），适用条件各异，而且都有证明过程。
如果不打算熟记证明，仅仅是应用，遇到具体场景再去回忆适用于哪种算法不太方便。
以下内容以手头的机械工业出版社基于原书第2版的译本整理了一下，便于速查。
不包含思考题、标注为“*”的章节和习题内容。
符号定义
一般地，
图G=(V, E)，其中V代表顶点集合，E代表边集合。ω(u, v)代表从顶点u到顶点v的边的权值。
如果ω(u, v)总为1，则称G为不加权的图。
补充定义
- DAG：有向无回路图
- 拓扑排序：将DAG的节点按照一定规则输出：当有u到v的边，则u在v前面。
- 强连通分支：对于图G(V, E)，如果一个顶点集合C⊆G，其中每对顶点u和v，u和v相互都是可以到达的，那么称C是G的一个强连通分支
- 最小生成树：无向连通图G的子集T，包含了所有顶点，且边的权值之和为最小。
- 松弛技术：对于s顶点，d[v]表示s到v的距离。如果d[v] > d[u] + ω(u,v)，则更新d[v] = d[u] + ω(u,v)
- 最大流：对于包含源节点和汇节点的有向非负权图，最大的流量
- 最大二分匹配：对于图G=(V,E)，存在边的子集M⊆E，满足所有v∈V，M中最多有一条边与v关联。最大匹配是最大势的匹配，即不存在一个边数更多的M\’。
速查表
| 算法名称 | 适用范围 | 核心思想 | 基本步骤 | 时间复杂度 | 备注 |
|---|---|---|---|---|---|
| 广度优先搜索BFS | 有向图/无向图，不涉及权重 | 1.队列 2.顶点按是否访问过着色 | 依次访问一个节点的所有相邻顶点，访问时着色并加入队列。每次循环从队列出队。 | O(V+E) | 可计算不加权的图最短路径 |
| 深度优先搜索DFS) | 有向图/无向图，不涉及权重 | 1.递归 2.顶点按是否访问过着色 | 依次访问一个节点的所有相邻顶点，访问时着色并递归访问它的相邻顶点。 | O(V+E) | |
| 拓扑排序(DFS) | DAG | DFS | 执行DFS，当一个顶点DFS完成时插入链表头，这个链表就是拓扑排序结果 | O(V+E) | |
| 计算强连通分支(DFS) | DAG | DFS | 执行DFS，对图G倒置后按照节点访问次序的降序再计算一次DFS，第二次DFS的生成树即为强连通分支 | O(V+E) | |
| 最小生成树-Kruskal算法 | 无向连通图 | 贪心算法 | 节点集合A初始化为空集，每次选一条安全边加入A。具体的，初始化每个节点都是一个集合，每次取最小权值的边，满足它的节点(u，v)所在集合不相等，此时令A=A∪{(u,v)} | O(ElgV) | |
| 最小生成树-Prim算法 | 无向连通图 | 贪心算法 | 节点集合A初始化为空集，每次选一条安全边加入A。具体的，初始化所有节点距离A为正无穷，先在A加入一个节点，距离A为0。每次取一个离集合A中所有顶点中最近的边，加入它和它的顶点u，并将u的所有相邻节点v的距离更新一次(新距离=min(u到v, key(v)))，直到所有顶点都加入了A | O(ElgV)，可以改进到O(E+VlgV) | |
| 单源最短路径-Bellman-Ford算法 | 有向图，权重可为负 | 松弛技术 | 松弛多次，次数为顶点数-1 | O(VE) | 如果有负权回路，返回值false。可用于差分约束问题求解。 |
| 单源最短路径-DAG | DAG | 拓朴排序、松弛技术 | 拓朴排序，按序取顶点，对它的所有临边松弛 | O(V+E) | |
| 单源最短路径-Dijkstra算法 | 有向图，边权重非负 | 松弛技术 | 顶点集合S初始化为空集，加入源节点s。选取距离S整体最近的顶点u，松弛u的所有相邻顶点v，直到所有顶点都并入S | O((V+E)lgV) | 可以用斐波那契堆优化至O(VlgV+E) |
| 每对顶点最短路径-Floyd-Warshall算法 | 有向图 | 动态规划 | 三重循环，k、i、j -> 1 to n, d(k)(i)(j) = min(d(k-1)(i)(j), d(k-1)(i)(k) + d(k-1)(j)(k)) | O(n^3) | |
| 每对顶点最短路径-Johnson算法 | 有向图，稀疏图，边权重非负 | 重赋权，Dijkstra + Bellman-Ford | 较为复杂，略 | O(V^2lgV+VE) | |
| 最大流-Ford-Fulkerson方法 | 有向图，边权重非负，包含源节点和汇顶点 | 依赖三种思想及其对应实现 | 较为复杂，略 | 基本算法为O(E|f*|) | 本书只介绍了基本算法、Edmods-Karp算法等。可用于解最大二分匹配问题 |
后注
每对顶点间最短路径也可以用Dijkstra和Bellman-Ford解决但不是最优，具体分析略。
附：图相关的NP完全问题
不详细介绍问题的含义。
- 团问题
- 顶点覆盖问题，在35章介绍了近似算法
- 哈密顿回路问题
- 旅行商问题，在35章介绍了近似算法
版权声明：本文为wuyuegb2312原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。