当前页面位置: » 丰搜网 » 文档中心 » 详细内容
最小耗费生成树
1. kruskal算法
(1) 算法思想
k r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。k r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
考察图1-12a 中的网络。初始时没有任何边被选择。图13-12b 显示了各节点的当前状态。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了k r u s k a l算法的伪代码。
/ /在一个具有n 个顶点的网络中找到一棵最小生成树
令t为所选边的集合，初始化t=
令e 为网络中边的集合
w h i l e(e≠ )&&( t ≠n- 1 ) {
令(u,v)为e中代价最小的边 e=e- { (u,v) } / /从e中删除边
i f( (u,v)加入t中不会产生环路)将（ u,v）加入t
}
i f( t = =n-1) t是最小耗费生成树
e l s e 网络不是互连的，不能找到生成树
(2) 正确性证明
利用前述装载问题所用的转化技术可以证明图1 3 - 1 3的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点： 1) 只要存在生成树，k r u s k a l算法总能产生一棵生成树； 2) 产生的生成树具有最小耗费。令g为任意加权无向图（即g是一个无向网络）。从1 2 . 11 . 3节可知当且仅当一个无向图连通时它有生成树。而且在kruskal 算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果g在开始时是连通的，则t与e中的边总能形成一个连通图。也就是若g开始时是连通的，算法不会终止于e= 和 t < n- 1。
现在来证明所建立的生成树t具有最小耗费。由于g具有有限棵生成树，所以它至少具有一棵最小生成树。令u为这样的一棵最小生成树， t与u都刚好有n- 1条边。如果t=u, 则t就具有最小耗费，那么不必再证明下去。因此假设t≠u，令k(k >0) 为在t中而不在u中的边的个数，当然k 也是在u中而不在t中的边的数目。 通过把u变换为t来证明u与t具有相同的耗费，这种转化可在k 步内完成。每一步使在t而不在u中的边的数目刚好减1。而且u的耗费不会因为转化而改变。经过k 步的转化得到的u将与原来的u具有相同的耗费，且转化后u中的边就是t中的边。由此可知， t具有最小耗费。每步转化包括从t中移一条边e 到u中，并从u中移出一条边f。边e 与f 的选取按如下方式进行：
