在例 及 中已考察过这个问题因为具有n 个顶点的无向网络G的每个生成树刚好具有n条边所以问题是用某种方法选择n条边使它们形成G的最小生成树至少可以采用三种不同的贪婪策略来选择这n条边这三种求解最小生成树的贪婪算法策略是 K r u s k a l算法P r i m算法和S o l l i n算法
Kruskal算法
() 算法思想
K r u s k a l算法每次选择n 条边所使用的贪婪准则是从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中注意到所选取的边若产生环路则不可能形成一棵生成树K r u s k a l算法分e 步其中e 是网络中边的数目按耗费递增的顺序来考虑这e 条边每次考虑一条边当考虑某条边时若将其加入到已选边的集合中会出现环路则将其抛弃否则将它选入
考察图a 中的网络初始时没有任何边被选择图b 显示了各节点的当前状态边( )是最先选入的边它被加入到欲构建的生成树中得到图 c下一步选择边( )并将其加入树中(如图 d所示)然后考虑边( )将它加入树中并不会产生环路于是便得到图 e下一步考虑边( )并将其加入树中(如图 f所示)在其余还未考虑的边中()具有最小耗费因此先考虑它将它加入正在创建的树中会产生环路所以将其丢弃此后将边( )加入树中得到的树如图g 所示下一步考虑边( )由于会产生环路将其丢弃最后考虑边( )并将其加入树中产生了一棵生成树其耗费为 图 给出了K r u s k a l算法的伪代码
/ /在一个具有n 个顶点的网络中找到一棵最小生成树
令T为所选边的集合初始化T=
令E 为网络中边的集合
w h i l e(E≠ )&&(| T |≠n ) {
令(uv)为E中代价最小的边 E=E { (uv) } / /从E中删除边
i f( (uv)加入T中不会产生环路)将( uv)加入T
}
i f(| T | = =n) T是最小耗费生成树
e l s e 网络不是互连的不能找到生成树
图 Kruskao算法的伪代码
() 正确性证明
利用前述装载问题所用的转化技术可以证明图 的贪婪算法总能建立一棵最小耗费生成树需要证明以下两点 ) 只要存在生成树K r u s k a l算法总能产生一棵生成树; ) 产生的生成树具有最小耗费令G为任意加权无向图(即G是一个无向网络)从 节可知当且仅当一个无向图连通时它有生成树而且在Kruskal 算法中被拒绝(丢弃)的边是那些会产生环路的边删除连通图环路中的一条边所形成的图仍是连通图因此如果G在开始时是连通的则T与E中的边总能形成一个连通图也就是若G开始时是连通的算法不会终止于E= 和| T |< n
现在来证明所建立的生成树T具有最小耗费由于G具有有限棵生成树所以它至少具有一棵最小生成树令U为这样的一棵最小生成树 T与U都刚好有n 条边如果T=U 则T就具有最小耗费那么不必再证明下去因此假设T≠U令k(k >) 为在T中而不在U中的边的个数当然k 也是在U中而不在T中的边的数目 通过把U变换为T来证明U与T具有相同的耗费这种转化可在k 步内完成每一步使在T而不在U中的边的数目刚好减而且U的耗费不会因为转化而改变经过k 步的转化得到的U将与原来的U具有相同的耗费且转化后U中的边就是T中的边由此可知 T具有最小耗费每步转化包括从T中移一条边e 到U中并从U中移出一条边f边e 与f 的选取按如下方式进行
) 令e 是在T中而不在U中的具有最小耗费的边由于k >这条边肯定存在
) 当把e 加入U时则会形成唯一的一条环路令f 为这条环路上不在T中的任意一条边
由于T中不含环路因此所形成的环路中至少有一条边不在T中
从e 与f 的选择方法中可以看出 V=U+ {e} { f } 是一棵生成树且T中恰有k 条边不在V中出现现在来证明V的耗费与U的相同显然V的耗费等于U的耗费加上边e 的耗费再减去边f 的耗费若e 的耗费比f 的小则生成树V的耗费比U的耗费小这是不可能的如果e 的耗费高于f在K r u s k a l算法中f 会在e 之前被考虑由于f 不在T中Kruskal 算法在考虑f 能否加入T时已将f 丢弃因此f 和T中耗费小于或等于f 的边共同形成环路通过选择e所有这些边均在U中因此U肯定含有环路但是实际上这不可能因为U是一棵生成树e 的代价高于f 的假设将会导致矛盾剩下的唯一的可能是e 与f 具有相同的耗费由此可知V与U的耗费相同
() 数据结构的选择及复杂性分析
为了按耗费非递减的顺序选择边可以建立最小堆并根据需要从堆中一条一条地取出各边当图中有e 条边时需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边边的集合T与G中的顶点一起定义了一个由至多n 个连通子图构成的图用顶点集合来描述每个子图这些顶点集合没有公共顶点为了确定边( uv)是否会产生环路仅需检查uv 是否在同一个顶点集中(即处于同一子图)如果是则会形成一个环路;如果不是则不会产生环路因此对于顶点集使用两个F i n d操作就足够了当一条边包含在T中时个子图将被合并成一个子图即对两个集合执行U n i o n操作集合的F i n d和U n i o n操作可利用 节的树(以及加权规则和路径压缩)来高效地执行F i n d操作的次数最多为eUn i o n操作的次数最多为n (若网络是连通的则刚好是n 次)加上树的初始化时间算法中这部分的复杂性只比O (n+e) 稍大一点
对集合T所执行的唯一操作是向T中添加一条新边T可用数组t 来实现添加操作在数组的一端进行因为最多可在T中加入n 条边因此对T的操作总时间为O (n)
总结上述各个部分的执行时间可得图 算法的渐进复杂性为O (n+el o ge)
() 实现
利用上述数据结构图 可用C + +代码来实现首先定义E d g e N o d e类(见程序 )它是最小堆的元素及生成树数组t 的数据类型
程序 Kruskal算法所需要的数据类型
template
class EdgeNode {
p u b l i c :
operator T() const {return weight;}
p r i v a t e :
T weight;//边的高度
int u v;//边的端点
} ;
为了更简单地使用 节的查找和合并策略定义了U n i o n F i n d类它的构造函数是程序 的初始化函数U n i o n是程序 的加权合并函数F i n d是程序 的路径压缩搜索函数
为了编写与网络描述无关的代码还定义了一个新的类U N e t Wo r k它包含了应用于无向网络的所有函数这个类与U n d i r e c t e d类的差别在于U n d i r e c t e d类中的函数不要求加权边而U N e t Wo r k要求边必须带有权值U N e t Wo r k中的成员需要利用N e t w o r k类中定义的诸如B e g i n和N e x t Ve r t e x的遍历函数不过新的遍历函数不仅需要返回下一个邻接的顶点而且要返回到达这个顶点的边的权值这些遍历函数以及有向和无向加权网络的其他函数一起构成了W N e t w o r k类(见程序 )
程序 WNetwork类
template
class WNetwork : virtual public Network
{
public :
virtual void First(int i int& j T& c)=;
virtual void Next(int i int& j T& c)=;
} ;
象B e g i n和N e x t Ve r t e x一样可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类中加入函数F i r s t与N e x t现在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r k中派生而来由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p h类需要访问U N e t w o r k的成员所以这两个类还必须从U N e t Wo r k中派生而来U N e t Wo r k : : K r u s k a l的代码见程序 它要求将Edges() 定义为N e t Work 类的虚成员并且把U N e t Wo r k定义为E d g e N o d e的友元)如果没有生成树函数返回f a l s e否则返回t r u e注意当返回true 时在数组t 中返回最小耗费生成树
程序 Kr u s k a l算法的C + +代码
template
bool UNetwork ::Kruskal(EdgeNode t[])
{// 使用K r u s k a l算法寻找最小耗费生成树
// 如果不连通则返回false
// 如果连通则在t [ : n ]中返回最小生成树
int n = Ve r t i c e s ( ) ;
int e = Edges();
/ /设置网络边的数组
InitializePos(); // 图遍历器
EdgeNode *E = new EdgeNode [e+];
int k = ; // E的游标
for (int i = ; i <= n; i++) { // 使所有边附属于i
int j;
T c;
First(i j c);
while (j) { // j 邻接自i
if (i < j) {// 添加到达E的边
E[++k]weight = c;
E[k]u = i;
E[k]v = j;}
Next(i j c);
}
}
// 把边放入最小堆
MinHeap > H();
HInitialize(E e e);
UnionFind U(n); // 合并/搜索结构
// 根据耗费的次序来抽取<
