上一篇博文我们提到了图的最短路径问题: http://www.cnblogs.com/mm93/p/8434056.html 而最短路径问题可以说是这样的一个问题: 路已经修好了, 该怎么从这儿走到那儿? 但是在和图有关的问题中, 还有另一种有趣的问题: 修路的成本已经知道了, 该怎么修路才能尽可能节约成本, 同时将这些地方都连起来?
比如我们知道有这么几个城市, 它们互相之间还没有路:
经过实地考察后, 发现可以修的路以及各条路的修路成本如下:
但是我们的预算有限, 需要在修路时尽可能的省钱 (也就是尽量减小所有边的权重之和), 同时保证图中每一个城市总是能到达图中任意一个城市, 该怎么修路呢? 对于上图来说, 其中一个方案是这样的, 其总共的修路成本(即总权重) 为 8:
另一个方案是这样的, 略有不同, 不过总成本也是 8:
像这样的问题, 就是我们今天要讨论的最小生成树问题为了更准确地说明什么是最小生成树, 我们需要先了解一个概念: 连通对于一个无向图而言, 如果每个顶点到每个其它顶点都存在路径, 则该无向图是连通的而对于有向图而言, 道理相同又稍有变化, 在有向图中, 若每个顶点到每个其它顶点都存在可行的路径, 则该有向图是强连通的比如下图就不是一个强连通的有向图, 其中非 v0 顶点无法到达 v0 顶点:
但是如果我们将上面这个有向图的边都变为无向边, 我们就会得到一个无向图, 此无向图即该有向图的基础图 (underlying graph) 如果一个有向图非强连通, 但是其基础图是连通的, 我们就称该有向图是弱连通的上面这个有向图就是一个弱连通的有向图
明白了什么是连通之后, 接下来我们说说最小生成树是什么: 在一个连通的无向图的所有边中, 挑选出足以使所有顶点连通的那些边, 且这些边的总权重不能更低, 则这些边与所有顶点构成的图就是最小生成树最小的意思是其总权重是最小的, 生成则是因为这个树是从一个无向图中找出来的, 也即生成的
等等_(:з)_ 不是说这些边与所有顶点构成的图吗, 怎么就成了树? 原因是这样的, 如果一个无向图是连通的, 那么我们就能找出满足上述条件的那个图, 而如果那个图存在, 那它一定是一棵树(树是特殊的图嘛, 这一点应该要懂的), 比如本文前面所找出的最小生成图, 显然是一棵树:
为什么称最后找出来的顶点与边的集合为最小生成树, 我们已经知道了, 而为什么最后找出来的一定是树咱能不纠结吗 (.)
好了, 接下来讨论下一个问题: 有向图可以找出最小生成树吗? 答案是可以, 只要有向图是强连通的并且寻找有向图的最小生成树的过程也是基本一样的, 因为无向图本就是以有向图的形式存储的 (一条无向边拆成两条有向边) 不过因为本文并不打算给出可运行的代码, 所以我们的讨论以无向图为基准, 主要关注算法的思路, 并且不考虑所给图非连通的情况
想要在图中找出最小生成树, 有两种算法可供选择: Prim 算法和 Kruskal 算法因为 Prim 算法与寻找最短路径的 Dijkstra 算法非常非常非常像, 所以我们先来讨论一下 Prim 算法
Prim 算法的思路是这样的:
1. 任选一个顶点, 将其标为已知, 即表示该顶点已在树中(Dijkstra 算法中, 起点由我们指定)
2. 找出所有已知顶点邻接的未知顶点, 其中与任一已知顶点的邻接边权重最小的未知顶点, 我们将其标为已知, 同时将其 preV 设为与其邻接边最小的已知顶点, 且其 distance 设为该邻接边的权重(在 Dijkstra 算法中, 我们用的是指向, 因为要考虑到有向图的情况, 此外, Dijkstra 算法中, 我们将被标为已知的未知顶点的 distance 设为与其相连的已知顶点的 distance 加上边的权重)
3. 反复执行第二步, 直至不存在已知顶点邻接了未知顶点为止
抽象的说, Prim 算法就是随机选一个顶点, 将其拉进原先为空的树中, 然后不断地通过尽可能小的边将其他顶点拉进这棵树中
老样子, 上述说法晦涩难懂 (.)所以我们需要实际的走一遍来加深一下理解, 以下图为例:
假设我们以 v3 作为起点, 则图初始化后的状态如下(顶点旁有红圈表示该顶点已知, 红圈中即该顶点的 preV, 顶点的 distance 我们暂不考虑):
接着, 我们找出所有已知顶点 (v3) 邻接的所有未知顶点: v0v1v2v4v5v6 发现与已知顶点邻接边最小的未知顶点是 v1v4, 其中未知顶点 v1 与已知顶点 v3 的邻接边权重为 1, 未知顶点 v4 与已知顶点 v3 的邻接边权重也为 1, 我们任选其一即可, 比如选择 v1, 然后将 v1 设为已知, v1.preV=v3:
继续, 我们找出所有已知顶点 (v1v3) 邻接的所有未知顶点: v0v2v4v5v6, 发现与已知顶点邻接边最小的未知顶点是 v0v4, 其中未知顶点 v0 与已知顶点 v1 的邻接边权重为 1, 未知顶点 v4 与已知顶点 v1 或 v3 的邻接边权重为 1, 我们任选其一, 比如 v4, 然后将 v4 设为已知, v4.preV=v1(也可以是 v4.preV=v3):
继续, 我们找出所有已知顶点 (v1v3v4) 邻接的所有未知顶点: v0v2v5v6, 发现与已知顶点邻接边最小的未知顶点是 v0v6, 其中未知顶点 v0 与已知顶点 v1 的邻接边权重为 1, 未知顶点 v6 与已知顶点 v4 的邻接边权重为 1, 我们选 v6, 将 v6 设为已知, v6.preV=v4:
继续, 我们找出所有已知顶点邻接的所有未知顶点: v0v2v5, 其中与已知顶点的邻接边最小的是 v0, 未知顶点 v0 与已知顶点 v1 的邻接边权重为 1, 我们将 v0 设为已知, v0.preV=v1:
继续, 找出所有已知顶点邻接的所有未知顶点: v2v5, 发现其中未知顶点 v5 与已知顶点 v6 的邻接边权重最小为 2, 所以我们将 v5 设为已知, v5.preV=v6:
继续, 找出所有已知顶点邻接的所有未知顶点: v2, 其中未知顶点 v2 与已知顶点 v5 的邻接边权重最小, 所以我们将 v2 设为已知, v2.preV=v5:
继续, 发现已经没有哪个已知顶点邻接了未知顶点, 所以算法结束
接下来, 我们只要进行这两步操作就可以得出最小生成树:
1. 将每个顶点与其 preV 相连的边标为已知
2. 将非已知的边删去
将每个顶点与其 preV 相连的边标为已知(注意, v3 的 preV 是自身, 此情况我们不做任何操作即可):
删去非已知的边:
当然, 在实际编程中, 有可能并不会执行这两个操作, 我们只要在将最小生成树的相关信息保存在 pathTable 中即可, 本例中算法结束后 pathTable 应为如下(与 Dijkstra 算法使用的 pathTable 略有不同: 没有 distance 域):
当然, 我们也可以使用和 Dijkstra 算法时一样的 pathTable, 即加上 distance 域, 不过在计算最小生成树时, 一个顶点的 distance 域应该是其与 preV 邻接的边的权重:
在我们走一遍 Prim 算法时, 我们发现 v4.preV 既可以设为 v3, 也可以设为 v1, 这就已经说明了一点: 一个图的最小生成树并不一定是唯一的不过还要注意的是: 一个图即便有多个最小生成树, 它们的总权重也应该是一样的
如果你回顾一遍 Prim 算法和 Dijkstra 算法, 就会发现, Prim 算法与 Dijkstra 算法的区别可以说就两个:
1.Prim 算法的起点是任选的, Dijkstra 算法是给定的(毕竟要找的是单源最短路径)
2.Prim 算法在将一个未知顶点设为已知时, 其 distance 设为其与已知顶点的最小邻接边的 weight, 而 Dijkstra 算法则是设为已知顶点. distance+weight
换句话说, Prim 算法就是稍稍修改了一下的 Dijkstra 算法如果你仔细观察我们用 Prim 算法生成的树, 你会发现从 v3 出发到任意顶点的路径恰好是 v3 到该顶点的最短路径:
接下来本应讨论 Kruskal 算法, 但是我忽然发现我之前忘了写一篇关于树的集合与不相交集的博文 (ˍ) 如果要讨论 Kruskal 算法, 这两个预备知识是必不可少的, 而如果这两个知识也要讲解的话, 博文就太长了 Orz 所以我只简单说说 Kruskal 的思路
在 Prim 算法中, 我们是以已知顶点 (即已在最小生成树中的顶点) 为基础, 不断地将未知顶点拉进树中而 Kruskal 算法则是另一种思路: 以当前最小的边为基础, 不断地将未知顶点拉进树中(这个过程可能产生多棵树)
以下图为例, 我们走一遍 Kruskal 算法:
首先, 我们需要将边按权重从小到大排序, 才能找当前最小边:
先是处理当前最小边[v0,v1], 其所连接的两个顶点均未知, 所以我们将它们均设为已知, 并连起来:
然后处理下一个当前最小边[v1,v3], 其所连接的 v3 未知, 将 v3 设为已知, 连起来:
接着处理边[v3,v4], 其连接的 v4 未知, 将 v4 设为已知, 连起来:
接着处理边[v1,v4], 其连接的两个顶点均为已知, 故跳过
接着处理边[v4,v6], 其连接的 v6 未知, 将 v6 设为已知, 连起来:
接着处理边[v2,v5], 其连接的 v2 和 v5 均为未知, 所以将 v2v5 均设为已知, 连起来(注意, 此时产生了两棵树):
接着处理边[v5,v6], 其连接的顶点均为已知, 但是 v5 和 v6 处于不同的树, 所以我们将其连起来(这部分的相关判断和处理需要树的集合知识, 以及不相交集数据结构):
接下来处理的所有边都是所连接顶点已知, 且所连接顶点处于同一棵树中, 所以均会跳过, 然后算法结束
没有掌握住博文的顺序和铺垫, 实在是失败
不过 Kruskal 算法的思路我想我应该讲清楚了, 就是 Dijkstra 算法和 Prim 算法的讲解可能太生硬了一些, 但是细细地读细细地理解细细地过一遍, 应该还是能明白的ω
这个系列的博文的主体部分到这儿就算结束了, 从第一篇博文一路看到这儿的话, 基本的数据结构和算法应该都能掌握而像什么 B + 树红黑树算法设计技巧等更特殊的知识我没有算在主体部分中, 以后可能会以浅入浅出数据结构 (附) 的标题形式写出
来源: https://www.cnblogs.com/mm93/p/8437939.html