加载中…
正文 字体大小:

Kruskal算法证明及实现

(2012-02-20 09:00:57)
标签:

杂谈

1、算法概述
用于生成连通无向图的最小代价生成树。
2、算法步骤
步骤一:T是边的集合,其初始状态为空;
步骤二:从原图剩余边中选取一条最小代价的边;
步骤三:看其是否与当前T中其它边构成环路;
步骤四:如果未构成环路,则加入T中;否则,丢弃该边;
步骤五:是否还有剩余边,如果有则返回步骤二,否则,程序结束。
3、算法证明
要证明Kruskal算法生成的是最小生成树,我们分两步来证明:
(1)Kruskal算法一定能得到一个生成树;
(2)该生成树具有最小代价。
证明如下:
(1)假设该算法得到的不是生成树,根据树的定义,就有两种情形,第一是得到的图是有环的,第二就是得到的图是不连通的。由于算法要求每次加入边都是无环的,所以第一种情形不存在,下面就只需证明第二种情形不存在即可。
假设得到的图是不连通的,则至少包含两个独立的的边集,假设其中一个为E,则E中边对应的所有点都无法到达其它边集对应的点(否则,根据算法定义,相应的联系边应被加入树中),而这与原图是连通的产生矛盾,因此,第二种情形也不可能存在。得证。
(2)假设图有n个顶点,则生成树一定具有n-1条边.由于图的生成树个数是有限的,所以至少有一棵树具有最小代价,假设该树为U。先做出如下假设:
1)得到的树为T。
2)U和T中不同的边的条数为k,其它n-1-k条边相同,这n-1-k条边构成边集E。;
3)在T中而不在U中的边按代价从小到大依次为a1,a2,...,ak。
4)在U中而不在T中的边按代价从小到大依次为x1,x2,...,xk。
现在我们通过把U转换为T(把T的边依次移入U中),来证明U和T具有相同代价。
首先,我们将a1移入U中,由于U本身是一棵树,此时任意加一条边都构成回路,所以a1的加入必然产生一条回路,且这条回路必然包括x1,x2,...,xk中的边。(否则a1与E中的边构成回路,而E也在T中,这与T中无回路矛盾。)
在这个回路中删除属于x1,x2,...,xk且代价最大边xi构成一个新的生成树V。
假设a1代价小于xi,则V的代价小于U,这与U是最小代价树矛盾,所以a1不可能小于xi。
假设a1大于xi,按照Kruskal算法,首先考虑代价小的边,则执行Kruskal算法时,xi应该是在a1之前考虑,而a1又在a2,...,ak之前考虑,所以考虑xi之前,T中的边只能是E中的边,而xi既然没加入树T,就说明xi必然与E中的某些边构成回路,但xi和E又同时在U中,这与U是生成树矛盾,所以a1也不可能大于xi。
因此,新得到的树V与T具有相同代价。
依次类推,把a1,a2,...,ak的边逐渐加到U中,最终得到的树(T)与U代价相同。
证明结束。





0

阅读 评论 收藏 转载 喜欢 打印举报
前一篇:数组声明
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇数组声明
      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有