最小生成树的两种寻路算法及证明[上]

  1. 云栖社区>
  2. 博客>
  3. 正文

最小生成树的两种寻路算法及证明[上]

一坨翔 2018-03-08 10:58:55 浏览4509
展开阅读全文

首先,什么是平面连通图?

平面连通图是一个二维网络,网络由节点和边组成,比如我随手画了一个:
_2018_03_08_10_49_16
也可以是这样:
_2018_03_08_10_50_30
它并不是一个空间连通图因为他可以拓扑变换成这样:
_2018_03_08_10_51_00
但如果这种图就不行了:
_2018_03_08_10_51_29
这样的连通图只能出现在三维空间中,所以无法满足欧拉公式.

其次,欧拉公式是沃特?

   欧拉公式也叫欧拉定理,指在简单多面体上,棱数(边)、面数和点数具有一定的关系:点+面=边+2。而且规定,平面网络属于特殊的一种多面体,想不到吧(关于欧拉定理的详解,请转向我的另一篇论文《浅谈欧拉定理》),这里要注意一下,数面数的时候要算上整个图外侧的那个无穷大的面,也就是环路的数量加上1。因此平面连通图恒满足欧拉定理。
   至于我为什么要介绍欧拉公式呢,是为了做准备,后面的最小生成树需要用到它!

然后,生成树有啥特点?

   在平面连通图中,我们想要用一个如树枝一般层层分岔但无环的线路经过所有的节点,且这个线路必须被包含于连通图。换个说法就是,在这个连通图中,我们希望删除掉一些边,让剩下所有的边都没有形成环,且剩下的边必须相互连通,不能被隔绝,这就是生成树(spanning tree)。比如这样:

_2018_03_08_10_52_29

   可以看出,不同的删边方法可以得到不同的生成树。
   根据欧拉公式,生成树中的面数为1,点数不变还是n,因而得到边数等于n-1,对于连通图中的所有生成树都成立。
   还是根据欧拉公式可以证明,此时在生成树中随便增添一条边(这条边当然要属于原连通图中),都必然将多出一个环,增加n条边就产生n个环。
   把这张连通图看成一张地图,每个节点都是一个地点,每条边都是可走的路径,这时给每条路径赋予一个权重值,代表这条路径的长短,这在TCP/IP协议中叫做度量值或开销(cost),所以这里权值越大,路径开销反而越大。
   因此,不同的生成树的总开销未必相同,其中总开销最小的就成为了本文探讨的最小生成树。
   还可以看出,在树上,任意两点之间走的路径是最短距离(放之于原来的连通图比较来说)的可能性很小。所以最小生成树不是地图上寻路的最好方法。

之后,求最小生成树的两种重要算法

   以上都是最基础的铺垫部分,写教程就这点麻烦,一定要从知识的根源开始讲起。那么废话不再多说,直接上算法:kruskal(克鲁斯卡尔)算法和prim(普利木)算法。这两个算法是计算最小生成树最常用的算法没有之一,因为他们既简单又完美,况且他们有很多的相似之处。

Kruskal Algorithm

前期准备:

   记平面连通图为G(Graph),设有n个节点,x条边。给所有的边编号并按照权重从小到大排序(有并列相等的顺序随便)放入集合A中,设一个容量为n-1的集合B用来存放最小生成树的所有边,设一个容量为x-n+1的集合C用来存放G中被删除掉的边。

kruskal算法是由一个个递进的循环周期组成的,每个循环周期的步骤如下:

   先从A中取出权重最小(权重相等选编号更小的)的边放入B中,同时要保证这条边不能和B中已有的边在G中构成环路,如果它是会构成环路的边,它将进入C,然后选择剩下最小权重的边。以此循环直到A中的边全部被取走。做成流程图就是酱紫的:

_2018_03_08_10_53_47
然后给一个过程图,大家自己意会:
_2018_03_08_10_54_30

   怎么样简单粗暴吧,虽然算法看上去简单的感人,但是该如何证明它的正确性呢?
   我们需要证明两点,第一:kruskal算出来的是生成树;第二:它是最小生成树。

证明它是个生成树:

根据之前对生成树下的定义,首先要覆盖所有点,其次不能有环,最后不能有断路。
第一点:很容易,既然通过集合A、B、C包含所有边的洗牌过程,自然照顾到了G中所有的点。
第二点:更容易,每个循环中都要检查一遍是否与之前的”小树苗“形成环路,最后肯定无环。
第三点:可以用反证法,假设最后生成了相互隔离的两棵树,因为总共循环了x次(每条边各一次),两棵树中间的那些边(C中可以连接两棵树的边)当初被审查的时候肯定会被纳入B,与“纳入C”矛盾,所以不可能生成两棵树。

证明它是最小生成树:

这个地方考验大家的空间想象能力,如果想不出来可以画图。
同样是反证法:

   对于一个连通图G,假如通过kruskal算法得到的生成树(记为K)不是最小生成树(记为T),那么由欧拉公式可知,”正真的”最小生成树T和通过kruskal算法得到的生成K树拥有相同的边数.那么设K中有y条边是T中没有的,反之T中也有y条边是K中没有的.无论是K还是T,在其中任意添加一条新边(属于G),都将产生一个环.

现在开始做一系列的变换,将K变换成T:

   选择T中K没有的一条边(记为L1)加入到K中,此时K中必然产生一个环!!,从这个环中选择另一条边(记为L2),删除之而打破这个环,而且L2必须是T中没有的(肯定存在这一条边因为T中的那一处无环!!!).以此类推,经过y次变换后K变成了总权重值更小的T.
   那么在上述过程中,肯定有一对L1L2中L1<L2,那么当初kruskal选路过程中,当选到L2的时候,意味着L2不会形成环切权最小,而此时L1也不会形成环,所以此时应该选择L1,与“选择L2”矛盾,得以证明假设不成立,所以kruskal算出来的是最小生成树。完。

prim算法见下文

网友评论

登录后评论
0/500
评论
一坨翔
+ 关注