现在来证明所建立的生成树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，在Kruskal算法中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
（loge）的时间来选取每一条边。
边的集合T与G中的顶点一起定义了一个由至多n
个连通子图构成的图。
用顶点集合来描述每个子图，这些顶点集合没有公共顶点。
为了确定边（u,v）是否会产生环路，仅需检查u,v
是否在同一个顶点集中（即处于同一子图）。
如果是，则会形成一个环路；如果不是，则不会产生环路。
因此对于顶点集使用两个Fin
d操作就足够了。
当一条边包含在T中时，2个子图将被合并成一个子图，即对两个集合执行Union操作。
集合的Find和U
nion操作可利用8.10.2节的树（以及加权规则和路径压缩）来高效地执行。
Find操作的次数最多为2e，Un
ion操作的次数最多为n-1（若网络是连通的，则刚好是n-1次）。
加上树的初始化时间，算法中这部分的复杂性只比O（n+e）
稍大一点。
对集合T所执行的唯一操作是向T中添加一条新边。
T可用数组t来实现。
添加操作在数组
的一端进行，因为最多可在T中加入n-1条边，因此对T的操作总时间为O（n）。
总结上述各个部分的执行时间，可得图13-13算法的渐进复杂性为O（n+eloge）。
（4）实现
利用上述数据结构，图1-13可用C++代码来实现。
首先定义EdgeNode类（见程序13-6
），它是最小堆的元素及生成树数组t的数据类型
----------------------------------------------
plot（100+t+15*cos（3.05*t）,t=0..200,coords=polar,axes=none,scaling=constrained）;
2004-5-2719:
42:
37
b
等级：
职业侠客
文章：
470
积分：
956
门派：
黑客帝国
注册：
2003-8-28
第12楼
程序13-6Kruskal算法所需要的数据类型
template
classEdgeNode{
public:
operatorT（）const{returnweight;}
private:
Tweight;//边的高度
intu,v;//边的端点
};
为了更简单地使用8.10.2节的查找和合并策略，定义了UnionFind类，它的构造函数是程序8-1
6的初始化函数，Union是程序8-16的加权合并函数，Find是程序8-17的路径压缩搜索函数。
为了编写与网络描述无关的代码，还定义了一个新的类UNetWork，它包含了应用于无向网络的所有函数。
这个类与Und
irected类的差别在于Undirected类中的函数不要求加权边，而UNetWor
k要求边必须带有权值。
UNetWork中的成员需要利用Network类中定义的诸如Begin和Ne
xtVerte
x的遍历函数。
不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的权值。
这些遍历函数以及有向和无向加权网络的其他函数一起构成了W
Network类（见程序13-7）。
程序13-7WNetwork类
template
classWNetwork:
virtualpublicNetwork
{
public:
virtualvoidFirst（inti,int&j,T&c）=0;
virtualvoidNext（inti,int&j,T&c）=0;
};
象Begin和NextVertex一样，可在AdjacencyWDigrap
h及LinkedWDigraph类中加入函数First与Next。
现在Adjace
ncyWDigraph及LinkedWDigraph类都需要从WNetWor
k中派生而来。
由于AdjacencyWGraph类和LinkedWGrap
h类需要访问UNetwork的成员，所以这两个类还必须从UNetWork中派生而来。
UNetWo
rk:
:
Kruskal的代码见程序13-8，它要求将Edges（）定义为NetWork
类的虚成员，并且把UNetWork定义为EdgeNode的友元）。
如果没有生成树，函数返回fals
e，否则返回true。
注意当返回true时，在数组t中返回最小耗费生成树。
程序13-8Kruskal算法的C++代码
template
boolUNetwork:
:
Kruskal（EdgeNodet[]）
{//使用Kruskal算法寻找最小耗费生成树
//如果不连通则返回false
//如果连通，则在t[0:
n-2]中返回最小生成树
intn=Vertices（）;
inte=Edges（）;
//设置网络边的数组
InitializePos（）;//图遍历器
EdgeNode*E=newEdgeNode[e+1];
intk=0;//E的游标
for（inti=1;i<=n;i++）{//使所有边附属于i
intj;
Tc;
First（i,j,c）;
while（j）{//j邻接自i
if（iE[++k].weight=c;
E[k].u=i;
E[k].v=j;}
Next（i,j,c）;
}
}
//把边放入最小堆
MinHeap>H
（1）;
H.Initialize（E,e,e）;
UnionFindU（n）;//合并/搜索结构
//根据耗费的次序来抽取边
k=0;//此时作为t的游标
while（e&&k//生成树未完成，尚有剩余边
EdgeNodex;
H.DeleteMin（x）;//最小耗费边
e--;
inta=U.Find（x.u）;
intb=U.Find（x.v）;
if（a!
=b）{//选择边
t[k++]=x;
U.Union（a,b）;}
}
DeactivatePos（）;
H.Deactivate（）;
return（k==n-1）;
}
2.Prim算法
与Kruskal算法类似，Pri
m算法通过每次选择多条边来创建最小生成树。
选择下一条边的贪婪准则是：
从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。
最终，在所有步骤中选择的边形成一棵树。
相反，在Kruskal
算法中所有入选的边集合最终形成一个森林。
Prim算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。
然后往T中加入一条代价最小的边（u,
v）使TÈ{（u,v）}仍是一棵树，这种加边的步骤反复循环直到T中包含n-1条边。
注意对于边（u,v），u、v
中正好有一个顶点位于T中。
Prim算法的伪代码如图1-1
4所示。
在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。
图1-15显示了对图1-12a使用Pri
m算法的过程。
把图1-14的伪代码细化为C++程序及其正确性的证明留作练习（练习31）。
//假设网络中至少具有一个顶点
设T为所选择的边的集合，初始化T=
设TV为已在树中的顶点的集合，置TV={1}
令E为网络中边的集合
while（E<>）&&（|T|<>n-1）{
令（u,v）为最小代价边，其中uTV,vTV
if（没有这种边）break
E=E-{（u,v）}//从E中删除此边
在T中加入边（u,v）
}
if（|T|==n-1）T是一棵最小生成树
else网络是不连通的，没有最小生成树
图13-14Prim最小生成树算法
如果根据每个不在TV中的顶点v选择一个顶点near（v），使得near（v）ÎTV且cost（v,n
ear（v））的值是所有这样的near（v）节点中最小的，则实现Prim算法的时间复杂性为O（n2
）。
下一条添加到T中的边是这样的边：
其cost（v,near（v））最小，且vTV。
3.Sollin算法
Solli
n算法每步选择若干条边。
在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。
在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。
将所选择的边加入要创建的生成树中。
注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。
当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。
开始时，所选择的边的集合为空。
若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。
图1-6给出了初始状态为图1-12a时，使用Sollin算法的步骤。
初始入选边数为0时的情形如图13-12a
时,森林中的每棵树均是单个顶点。
顶点1，2，.，7所选择的边分别是（1.6）,（2,7）,（3,4）,（4,3）,（5,4）,
（6,1）,（7,2），其中不同的边是（1,6），（2,7），（3,4）和（5,4
），将这些边加入入选边的集合后所得到的结果如图13-16a所示。
下一步具有顶点集{1,6}的树选择边（6,5
），剩下的两棵树选择边（2,3），加入这两条边后已形成一棵生成树，构建好的生成树见图13-6b。
Solli
n算法的C++程序实现及其正确性证明留作练习（练习32）。
----------------------------------------------
plot（100+t+15*cos（3.05*t）,t=0..200,coords=polar,axes=none,scaling=constrained）;
2004-5-2719:
42:
54
b
等级：
职业侠客
文章：
470
积分：
956
门派：
黑客帝国
注册：
2003-8-28
第13楼
练习
8.针对装载问题，扩充贪婪算法，考虑有两条船的情况，算法总能产生最优解吗？
9.已知n个任务的执行序列。
假设任务i需要ti个时间单位。
若任务完成的顺序为1，2，.，n，则任务i完成的时间为ci=i
åj=1tj。
任务的平均完成时间（AvergeCompletionTime,ACT）
为1–nnåi=1ci。
1）考虑有四个任务的情况，每个任务所需时间分别是（4，2，8，1）。
若任务的顺序为1，2，3，4，则ACT是多少？
2）若任务顺序为2，1，4，3，则ACT是多少？
3）创建具有最小ACT的任务序列的贪婪算法分n步来构造该任务序列，在每一步中，从剩下的任务里选择时间最小的任务。
对于1
），利用这种策略获得的任务顺序为4，2，1，3，这种顺序的ACT是多少？
4）写一个C++程序实现3）中的贪婪策略，程序的复杂性应为O（nlogn），试证明之。
5）证明利用3）中的贪婪算法获得的任务顺序具有最小的ACT。
10.若有两个工人执行练习9中的n个任务，需将任务分配给他们，同时他们具有自己的任务执行顺序。
任务完成时间及AC
T的定义同练习9。
使AC
T最小化的一种可行的贪婪算法是：
两个工人轮流选择任务，每次从剩余的任务中选择时间最小的任务。
每个人按照自己所选任务的顺序执行任务。
对于练习9中的例子，假定工人1首先选择任务4，然后工人2选择任务2，工人1选择任务1，最后工人2选择任务3。
1）利用C++程序实现这种策略，其时间复杂性为多少？
2）上述的贪婪策略总能获得最小的ACT吗？
证明结论。
11.1）考虑有m个人可以执行任务，扩充练习10中的贪婪算法。
2）算法能保证获得最优解吗？
证明结论。
3）用C++程序实现此算法，其复杂性是多少？
12.考虑例4-4的堆栈折叠问题。
1）设计一个贪婪算法，将堆栈折叠为最小数目的子堆栈，使得每个子堆栈的高度均不超过H。
2）算法总能保证得到数目最少的子堆栈吗？
证明结论。
3）用C++代码实现1）的算法。
4）代码的时间复杂性是多少？
13.编写C++程序实现0/1背包问题，使用如下启发式方法：
按价值密度非递减的顺序打包。
14.根据k=1的性能受限启发式方法编写一个C++程序来实现0/1背包问题。
15.对于k=1的情况证明用性能受限的启发式方法求解0/1背包问题会发生边界错误。
16.根据k=2的性能受限启发式方法编写一个C++程序来实现0/1背包问题。
17.考虑0≤xi≤1而不是xiÎ{0,1
}的连续背包问题。
一种可行的贪婪策略是：
按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包中装入此物品的一部分。
1）对于n=3,w=[100,10,10],p=[20,15,15]及c=105
上述装入方法获得的结果是什么？
2）证明这种贪婪算法总能获得最优解。
3）用一个C++程序实现此算法。
18.例13-1的渴婴问题是练习17中连续背包问题的一般化，将练习1
7的贪婪算法用于渴婴问题，算法能保证总能得到最优解吗？
证明结论。
19.1）证明当且仅当二分图没有覆盖时，图13-7的算法找不到覆盖。
2）给出一个具有覆盖的二分图，使得图13-7的算法找不到最小覆盖。
20.当第一步选择了顶点1时，给出图13-7的工作过程。
21.
对于二分图覆盖问题设计另外一种贪婪启发式方法，可使用如下贪婪准则：
如果B中的某一个顶点仅被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。
1）给出这种贪婪算法的伪代码。
2）编写一个C++函数作为Undirected类的成员来实现上述贪婪算法。
3）函数的复杂性是多少？
4）验证代码的正确性。
22.令G为无向图，S为G中顶点的子集，当且仅当S中的任意两个顶点都有一条边相连时，S为完备子图（cliqu
e），完备子图的大小即S中的顶点数目。
最大完备子图（maximum
clique）即具有最大项点数目的完备子图。
在图中寻找最大完备子图的问题（即最大完备子图问题）是一个NP-复杂问题。
1）给出最大完备子图问题的一种可行的贪婪算法及其伪代码。
2）给出一个能用1）中的启发式算法求解最大完备子图的图例，以及不能用该算法求解的一个图例。
3）将1）中的启发式算法实现为Undirected:
:
Clique（intC,intm）
共享成员，其中最大完备子图的大小返回到m中，最大完备子图的顶点返回到C中。
4）代码的复杂性是多少？
23.令G为一无向图，S为G中顶点的子集，当且仅当S中任意两个顶点都无边相连时，S为无关集（independent
set）。
最大无关集即是顶点数目最多的无关集。
在一幅图中寻找最大无关集是一个NP-复杂问
升级会员 