《算法导论》图相关算法小结

2019/04/10 10:10
阅读数 6

最近又抽空读了一遍《算法导论》,关于图的内容贯穿了多个章节(比如在动态规划一章埋了无权最短路径的伏笔,后面才专门讲),适用条件各异,而且都有证明过程。 如果不打算熟记证明,仅仅是应用,遇到具体场景再去回忆适用于哪种算法不太方便。

以下内容以手头的机械工业出版社基于原书第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完全问题

不详细介绍问题的含义。

  1. 团问题
  2. 顶点覆盖问题,在35章介绍了近似算法
  3. 哈密顿回路问题
  4. 旅行商问题,在35章介绍了近似算法

原文出处:https://www.cnblogs.com/wuyuegb2312/p/12390576.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部