c语言算法 - 贪婪算法 - 最小耗费生成树

c语言算法 - 贪婪算法 - 最小耗费生成树2010-01-28在例1-2及1-3中已考察过这个问题。因为具有n 个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。

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 网络不是互连的，不能找到生成树

图13-13 Kruskao算法的伪代码