id5.txt

介绍动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。

i f(| T | = =n-1) T是最小耗费生成树

e l s e 网络不是互连的，不能找到生成树

图13-13 Kruskao算法的伪代码

 

(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 的选取按如下方式进行：

1) 令e 是在T中而不在U中的具有最小耗费的边。由于k >0，这条边肯定存在。

2) 当把e 加入U时，则会形成唯一的一条环路。令f 为这条环路上不在T中的任意一条边。

由于T中不含环路，因此所形成的环路中至少有一条边不在T中。

从e 与f 的选择方法中可以看出， V=U+ {e} -{ f } 是一棵生成树，且T中恰有k- 1条边不在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的耗费相同。

(3) 数据结构的选择及复杂性分析

为了按耗费非递减的顺序选择边，可以建立最小堆并根据需要从堆中一条一条地取出各边。当图中有e 条边时，需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边。边的集合T与G中的顶点一起定义了一个由至多n 个连通子图构成的图。用顶点集合来描述每个子图，这些顶点集合没有公共顶点。为了确定边（ u,v）是否会产生环路，仅需检查u,v 是否在同一个顶点集中（即处于同一子图）。如果是，则会形成一个环路；如果不是，则不会产生环路。因此对于顶点集使用两个F i n d操作就足够了。当一条边包含在T中时，2个子图将被合并成一个子图，即对两个集合执行U n i o n操作。集合的F i n d和U n i o n操作可利用8 . 1 0 . 2节的树（以及加权规则和路径压缩）来高效地执行。F i n d操作的次数最多为2e，Un i o n操作的次数最多为n- 1（若网络是连通的，则刚好是n- 1次）。加上树的初始化时间，算法中这部分的复杂性只比O (n+e) 稍大一点。

对集合T所执行的唯一操作是向T中添加一条新边。T可用数组t 来实现。添加操作在数组

的一端进行，因为最多可在T中加入n- 1条边，因此对T的操作总时间为O (n)。

总结上述各个部分的执行时间，可得图1 3 - 1 3算法的渐进复杂性为O (n+el o ge)。

(4) 实现

利用上述数据结构，图1 - 1 3可用C + +代码来实现。首先定义E d g e N o d e类（见程序1 3 - 6 )，它是最小堆的元素及生成树数组t 的数据类型。

程序13-6 Kruskal算法所需要的数据类型

template <class T>

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;//边的端点

} ;

为了更简单地使用8 . 1 0 . 2节的查找和合并策略，定义了U n i o n F i n d类，它的构造函数是程序8 - 1 6的初始化函数，U n i o n是程序8 - 1 6的加权合并函数，F i n d是程序8 - 1 7的路径压缩搜索函数。

为了编写与网络描述无关的代码，还定义了一个新的类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类（见程序1 3 - 7）。

程序13-7 WNetwork类

template<class T>

class WNetwork : virtual public Network

{

public :

virtual void First(int i, int& j, T& c)=0;

virtual void Next(int i, int& j, T& c)=0;

} ;

象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的代码见程序1 3 - 8，它要求将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 中返回最小耗费生成树。

程序13-8 Kr u s k a l算法的C + +代码

template<class T>

bool UNetwork<T>::Kruskal(EdgeNode<T> t[])

{// 使用K r u s k a l算法寻找最小耗费生成树

// 如果不连通则返回false

// 如果连通，则在t [ 0 : n - 2 ]中返回最小生成树

int n = Ve r t i c e s ( ) ;

int e = Edges();

/ /设置网络边的数组

InitializePos(); // 图遍历器

EdgeNode<T> *E = new EdgeNode<T> [e+1];

int k = 0; // E的游标

for (int i = 1; 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<EdgeNode<T> > H(1);

H.Initialize(E, e, e);

UnionFind U(n); // 合并/搜索结构

// 根据耗费的次序来抽取边

k = 0; // 此时作为t的游标

while (e && k < n - 1) {

// 生成树未完成，尚有剩余边

EdgeNode<T> x;

H.DeleteMin(x); // 最小耗费边

e - - ;

int a = U.Find(x.u);

int b = U.Find(x.v);

if (a != b) {// 选择边

t[k++] = x;

U . U n i o n ( a , b ) ; }

}

D e a c t i v a t e P o s ( ) ;

H . D e a c t i v a t e ( ) ;

return (k == n - 1);

}

2. Prim算法

与Kr u s k a l算法类似，P r i m算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准则是：从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所有步骤中选择的边形成一棵树。相反，在Kruskal 算法中所有入选的边集合最终形成一个森林。

P r i m算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。然后往T中加入一条代价最小的边（ u , v）使Tè{ (u , v) }仍是一棵树，这种加边的步骤反复循环直到T中包含n- 1条边。注意对于边（ u , v），u、v 中正好有一个顶点位于T中。P r i m算法的伪代码如图1 -1 4所示。在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。图1 - 1 5显示了对图1-12a 使用P r i m算法的过程。把图1 - 1 4的伪代码细化为C + +程序及其正确性的证明留作练习（练习3 1）。

 

/ /假设网络中至少具有一个顶点

设T为所选择的边的集合，初始化T=

设T V为已在树中的顶点的集合，置T V= { 1 }

令E为网络中边的集合

w h i l e(E< > ) & & (| T | < > n-1) {

令（u , v）为最小代价