虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。
1.1最优化问题
本章及后续章节中的许多例子都是最优化问题（optimizationproblem），每个最优化问题都包含一组限制条件（constraint）和一个优化函数（optimizationfunction），符合限制条件的问题求解方案称为可行解（feasiblesolution），使优化函数取得最佳值的可行解称为最优解（optimalsolution）。
例1-1[渴婴问题]有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i种饮料，对它作出相对评价，将一个数值si作为满意度赋予第i种饮料。
通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i种饮料的总量（以盎司为单位），而此婴儿需要t盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？
设各种饮料的满意度已知。令xi为婴儿将要饮用的第i种饮料的量，则需要解决的问题是：
找到一组实数xi（1≤i≤n），使ni=1sixi最大，并满足：ni=1xi=t及0≤xi≤ai。
需要指出的是：如果ni=1ai 对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/输出作如下形式的描述： 输入：n，t，si，ai（其中1≤i≤n，n为整数，t、si、ai为正实数）。 输出：实数xi（1≤i≤n），使ni=1sixi最大且ni=1xi=t（0≤xi≤ai）。如果ni=1ai 在这个问题中，限制条件是ni=1xi=t且0≤xi≤ai，1≤i≤n。而优化函数是ni=1sixi。任何满足限制条件的一组实数xi都是可行解，而使ni=1sixi最大的可行解是最优解。 例1-2[装载问题]有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述：设存在一组变量xi，其可能取值为0或1。如xi为0，则货箱i将不被装上船；如xi为1，则货箱i将被装上船。我们的目的是找到一组xi，使它满足限制条件ni=1wixi≤c且xi{0,1},1≤i≤n。相应的优化函数是ni=1xi。 满足限制条件的每一组xi都是一个可行解，能使ni=1xi取得最大值的方案是最优解。 例1-3[最小代价通讯网络]城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。1.2算法思想 在贪婪算法（greedymethod）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。 例1-4[找零钱]一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩67美分，首先入选的是两枚25美分的硬币，第三枚入选的不能是25美分的硬币，否则硬币的选择将不可行（零钱总数超过67美分），第三枚应选择10美分的硬币，然后是5美分的，最后加入两个1美分的硬币。 贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。 例1-6[最短路径]给出一个有向网络，路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点s到达目的顶点d的最短路径。 贪婪算法分步构造这条路径，每一步在路径中加入一个顶点。假设当前路径已到达顶点q， 且顶点q并不是目的顶点d。加入下一个顶点所采用的贪婪准则为：选择离q最近且目前不在路径中的顶点。 这种贪婪算法并不一定能获得最短路径。例如，假设在图13-2中希望构造从顶点1到顶点5的最短路径，利用上述贪婪算法，从顶点1开始并寻找目前不在路径中的离顶点1最近的顶点。到达顶点3，长度仅为2个单位，从顶点3可以到达的最近顶点为4，从顶点4到达顶点2，最后到达目的顶点5。所建立的路径为1,3,4,2,5，其长度为10。这条路径并不是有向图中从1到5的最短路径。事实上，有几条更短的路径存在，例如路径1，4，5的长度为6。 能（boundedperformance）。具有限定性能的启发式方法称为近似算法（approximationalgorithm）。 本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。 1.3.1货箱装船 这个问题来自例1-2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。例1-7假设n=8,[w1,...w8]=[100,200,50,90,150,50,20,80],c=400。利用贪婪算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1,...,x8]=[1,0,1,1,0,1,1,1]且xi=6。 定理1-1利用贪婪算法能产生最佳装载。 证明可以采用如下方式来证明贪婪算法的最优性：令x=[x1,...,xn]为用贪婪算法获得的解，令y=[y1,...,yn]为任意一个可行解，只需证明ni=1xi≥ni=1yi。不失一般性，可以假设货箱都排好了序：即wi≤wi+1（1≤i≤n）。然后分几步将y转化为x，转换过程中每一步都产生一个可行的新y，且ni=1yi大于等于未转化前的值，最后便可证明ni=1xi≥nj=1yi。 根据贪婪算法的工作过程，可知在[0,n]的范围内有一个k，使得xi=1,i≤k且xi=0,i>k。寻找[1,n]范围内最小的整数j，使得xj≠yj。若没有这样的j存在，则ni=1xi=ni=1yi。如果有这样的j存在，则j≤k，否则y就不是一个可行解，因为xj≠yj，xj=1且yj=0。令yj=1，若结果得到的y不是可行解，则在[j+1,n]范围内必有一个l使得yl=1。令yl=0，由于wj≤wl，则得到的y是可行的。而且，得到的新y至少与原来的y具有相同数目的1。 程序13-1货箱装船 template voidContainerLoading(intx[],Tw[],Tc,intn) {//货箱装船问题的贪婪算法 //x[i]=1当且仅当货箱i被装载，1<=i<=n //c是船的容量,w是货箱的重量 //对重量按间接寻址方式排序 //t是间接寻址表 int*t=newint[n+1]; IndirectSort(w,t,n); //此时,w[t[i]]<=w[t[i+1]],1<=i //初始化x for(inti=1;i<=n;i++) x[i]=0; //按重量次序选择物品 for(i=1;i<=n&&w[t[i]]<=c;i++){ x[t[i]]=1; c-=w[t[i]];}//剩余容量 delete[]t; } 1.3.20/1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即ni=1pixi取得最大值。约束条件为ni=1wixi≤c和xi[0,1](1≤i≤n)。 在这个表达式中，需求出xt的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。0/1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。例1-8在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0/1背包问题进行建模，其中车对应于背包，货物对应于物品。 0/1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=[10,20],p=[5,100],c=25。当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。 还可以利用另一方案，价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选择可 装入包的pi/wi值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n=3,w=[20,15,15],p=[40,25,25],c=30时的最优解。 例13-9考虑n=4,w=[2,4,6,7],p=[6,10,12,13],c=11。当k=0时，背包按物品价值密度非递减顺序装入，首先将物品1放入背包，然后是物品2，背包剩下的容量为5个单元，剩下的物品没有一个合适的，因此解为x=[1,1,0,0]。此解获得的价值为16。 现在考虑k=1时的贪婪启发法。最初的子集为{1},{2},{3},{4}。子集{1},{2}产生与k=0时相同的结果，考虑子集{3}，置x3为1。此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1为1，这时仅剩下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集{3}开始求解得结果为x=[1,0,1,0]，获得的价值为18。若从子集{4}开始，产生的解为x=[1,0,0,1]，获得的价值为19。考虑子集大小为0和1时获得的最优解为[1,0,0,1]。这个解是通过k=1的贪婪启发式算法得到的。 1.3.3拓扑排序一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ActivityOnVertex,AOV）网络。有向图的顶点代表任务，有向边(i,j)表示先后关系：任务j开始前任务i必须完成。图1-4显示了六个任务的工程，边（1,4）表示任务1在任务4开始前完成，同样边（4,6）表示任务4在任务6开始前完成，边（1,4）与（4,6）合起来可知任务1在任务6开始前完成，即前后关系是传递的。由此可知，边（1,4）是多余的，因为边（1,3）和（3,4）已暗示了这种关系。 现在用贪婪算法来求解图1-4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V=2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V=25。下一步，顶点1是唯一的候选，因此V=251。第四步，顶点3是唯一的候选，因此把顶点3加入V 得到V=2513。在最后两步分别加入顶点4和6，得V=251346。 1.贪婪算法的正确性 为保证贪婪算法算的正确性，需要证明：1)当算法失败时，有向图没有拓扑序列；2)若 算法没有失败，V即是拓扑序列。2)即是用贪婪准则来选取下一个顶点的直接结果，1)的证明见定理13-2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qjqj+1.qkqj,则它没有拓扑序列，因为该序列暗示了qj一定要在qj开始前完成。 定理1-2如果图13-5算法失败，则有向图含有环路。 证明注意到当失败时|V| 2.数据结构的选择 为将图1-5用C++代码来实现，必须考虑序列V的描述方法，以及如何找出可加入V的候选顶点。一种高效的实现方法是将序列V用一维数组v来描述的，用一个栈来保存可加入V的候选顶点。另有一个一维数组InDegree，InDegree[j]表示与顶点j相连的节点i的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（i,j）。当InDegree[j]变为0时表示j成为一个候选节点。序列V初始时为空。InDegree[j]为顶点j的入度。每次向V中加入一个顶点时，所有与新加入顶点邻接的顶点j，其InDegree[j]减1。对于有向图1-4，开始时InDegree[1:6]=[0,0,1,3,1,3]。由于顶点1和2的InDegree值为0，因此它们是可加入V的候选顶点，由此，顶点1和2首先入栈。每一步，从栈中取出一个顶点将其加入V，同时减去与其邻接的顶点的InDegree值。若在第一步时从栈中取出顶点2并将其加入V，便得到了v[0]=2，和InDegree[1:6]=[0,0,1,2,0,3]。由于InDegree[5]刚刚变为0，因此将顶点5入栈。 程序13-2给出了相应的C++代码，这个代码被定义为Network的一个成员函数。而且，它对于有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针对有向图来定义的。为解决这个问题，利用同样的模板来定义成员函数AdjacencyGraph,AdjacencyWGraph，LinkedGraph和LinkedWGraph。这些函数可重载Network中的函数并可输出错误信息。如果找到拓扑序列，则Topological函数返回true；若输入的有向图无拓扑序列则返回false。当找到拓扑序列时，将其返回到v[0:n-1]中。 3.Network:Topological的复杂性 程序13-2拓扑排序 boolNetwork::Topological(intv[]) {//计算有向图中顶点的拓扑次序 //如果找到了一个拓扑次序，则返回true，此时，在v[0:n-1]中记录拓扑次序 //如果不存在拓扑次序，则返回false intn=Vertices(); //计算入度 int*InDegree=newint[n+1]; InitializePos();//图遍历器数组 for(inti=1;i<=n;i++)//初始化 InDegree[i]=0; for(i=1;i<=n;i++){//从i出发的边 intu=Begin(i); while(u){ InDegree[u]++; u=NextVertex(i);} //把入度为０的顶点压入堆栈 LinkedStack for(i=1;i<=n;i++) if(!InDegree[i])S.Add(i); //产生拓扑次序 i=0;//数组v的游标 while(!S.IsEmpty()){//从堆栈中选择 intw;//下一个顶点 S.Delete(w); v[i++]=w; intu=Begin(w); while(u){//修改入度 InDegree[u]--; if(!InDegree[u])S.Add(u); u=NextVertex(w);} DeactivatePos(); delete[]InDegree; return(i==n); 1.3.4二分覆盖二分图是一个无向图，它的n个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A'覆盖集合B（或简单地说，A'是一个覆盖）。覆盖A'的大小即为A'中的顶点数目。当且仅当A'是覆盖B的子集中最小的时，A'为最小覆盖。 例1-10考察如图1-6所示的具有17个顶点的二分图，A={1,2,3,16,17}和B={4,5,6,7,8,9,10,11,12,13,14,15}，子集A'={1,16,17}是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（bipartite-cover）问题。在例12-3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。 二分覆盖问题类似于集合覆盖（set-cover）问题。在集合覆盖问题中给出了k个集合S={S1,S2,.,Sk}，每个集合Si中的元素均是全集U中的成员。当且仅当èiS'Si=U时，S的子集S'覆盖U，S'中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S'为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1,.,Sk，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。 例1-11令S={S1，...，S5},U={4，5，...，15},S1={4，6，7，8，9，13}，S2={4，5，6，8}，S3={8，10，12，14，15}，S4={5，6，8，12，14，15}，S5={4，9，10，11}。S'={S1，S4，S5}是一个大小为3的覆盖，没有更小的覆盖，S'即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，16和17分别表示集合S1，S2，S3，S4和S5，顶点j表示集合中的元素j，4≤j≤15。 集合覆盖问题为NP-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是NP-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A'，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。 例1-12考察图1-6所示的二分图，初始化A'=且B中没有顶点被覆盖，顶点1和16均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和17分别覆盖四个。因此，在第一步往A'中加入顶点1或16，若加入顶点16，则它覆盖的顶点为{5,6,8,12,14,15}，未覆盖的顶点为{4,7,9,10,11,13}。顶点1能覆盖其中四个顶点（{4,7,9,13}），顶点2覆盖一个({4})，顶点3覆盖一个（{10}），顶点16覆盖零个，顶点17覆盖四个{4,9,10,11}。下一步可选择1或17加入A'。若选择顶点1，则顶点{10,11}仍然未被覆盖，此时顶点1，2，16不覆盖其中任意一个，顶点3覆盖一个，顶点17覆盖两个，因此选择顶点17，至此所有顶点已被覆盖，得A'={16,1,17}。 图1-7给出了贪婪覆盖启发式方法的伪代码，可以证明：1)当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2)启发式方法可能找不到二分图的最小覆盖。 1.数据结构的选取及复杂性分析 为实现图13-7的算法，需要选择A'的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A'仅使用加法运算，则可用一维整型数组C来描述A'，用m来记录A'中元素个数。将A'中的成员记录在C[0:m-1]中。对于A中顶点i，令Newi为i所能覆盖的B中未覆盖的顶点数目。逐步选择Newi值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各Newi值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j为这样的一个顶点，则A中所有覆盖j的顶点的Newi值均减1。 例1-13考察图1-6，初始时(New1,New2,New3,New16,New17)=(6,4,5,6,4)。假设在例1-12中，第一步选择顶点16，为更新Newi的值检查B中所有最近被覆盖的顶点，这些顶点为5,6,8,12,14和15。当检查顶点5时，将顶点2和16的Newi值分别减1，因为顶点5不再是被顶点2和16覆盖的未覆盖节点；当检查顶点6时，顶点1,2,和16的相应值分别减1；同样，检查顶点8时，1，2，3和16的值分别减1；当检查完所有最近被覆盖的顶点，得到的Newi值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和13；检查顶点4时，New1,New2,和New17的值减1；检查顶点7时，New1的值减1，因为顶点1是覆盖7的唯一顶点。 为了实现顶点选取的过程，需要知道Newi的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，New是一个整型数组，New[i]即等于Newi，且cov为一个布尔数组。若顶点i未被覆盖则cov[i]等于false，否则cov[i]为true。现将图1-7的伪代码进行细化得到图1-8。 m=0;//当前覆盖的大小 对于A中的所有i，New[i]=Degree[i] 对于B中的所有i，Cov[i]=false while(对于A中的某些i,New[i]>0){ 设v是具有最大的New[i]的顶点； C[m++]=v; for(所有邻接于v的顶点j){ if(!Cov[j]){ Cov[j]=true; 对于所有邻接于j的顶点，使其New[k]减1 }}} if(有些顶点未被覆盖)失败 else找到一个覆盖 图1-8图1-7的细化 2.降低复杂性 3.双向链接箱子的实现 为了实现上述双向链接箱子，图1-9定义了类Undirected的私有成员。NodeType是一个具有私有整型成员left和right的类，它的数据类型是双向链表节点，程序13-3给出了Undirected的私有成员的代码。 voidCreateBins(intb,intn) 创建b个空箱子和n个节点 voidDestroyBins(){delete[]node; delete[]bin;} voidInsertBins(intb,intv) 在箱子b中添加顶点v voidMoveBins(intbMax,intToBin,intv) 从当前箱子中移动顶点v到箱子ToBin int*bin; bin[i]指向代表该箱子的双向链表的首节点 NodeType*node; node[i]代表存储顶点i的节点 图1-9实现双向链接箱子所需的Undirected私有成员 程序13-3箱子函数的定义 voidUndirected::CreateBins(intb,intn) {//创建b个空箱子和n个节点 node=newNodeType[n+1]; bin=newint[b+1]; //将箱子置空 for(inti=1;i<=b;i++) bin[i]=0; voidUndirected::InsertBins(intb,intv) {//若b不为０，则将v插入箱子b if(!b)return;//b为0，不插入 node[v].left=b;//添加在左端 if(bin[b])node[bin[b]].left=v; node[v].right=bin[b]; bin[b]=v; voidUndirected::MoveBins(intbMax,intToBin,intv) {//将顶点v从其当前所在箱子移动到ToBin. //v的左、右节点 intl=node[v].left; intr=node[v].right; //从当前箱子中删除 if(r)node[r].left=node[v].left; if(l>bMax||bin[l]!=v)//不是最左节点 node[l].right=r; elsebin[l]=r;//箱子l的最左边 //添加到箱子ToBin InsertBins(ToBin,v); 函数CreateBins动态分配两个数组：node和bin，node[i]表示顶点i,bin[i]指向其New值为i的双向链表的顶点,for循环将所有双向链表置为空。如果b≠0，函数InsertBins将顶点v插入箱子b中。因为b是顶点v的New值，b=0意味着顶点v不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n加入New值为b的双向链表箱子的最前面，这种加入方式需要将node[v]加入bin[b]中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left置为b。若箱子不空，则当前第一个节点的left指针被置为指向新节点。node[v]的右指针被置为bin[b]，其值可能为0或指向上一个首节点的指针。最后，bin[b]被更新为指向表中新的第一个节点。MoveBins将顶点v从它在双向链表中的当前位置移到New值为ToBin的位置上。其中存在bMax，使得对所有的箱子bin[j]都有：如j>bMax，则bin[j]为空。代码首先确定node[v]在当前双向链表中的左右节点，接着从双链表中取出node[v]，并利用InsertBins函数将其重新插入到bin[ToBin]中。 4.Undirected::BipartiteCover的实现 函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L[i]=1表示顶点i在集合A中，L[i]=2则表示顶点在B中。函数有两个输出参数：C和m，m为所建立的覆盖的大小，C[0,m-1]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回false；否则返回true。完整的代码见程序13-4。 程序13-4构造贪婪覆盖 boolUndirected::BipartiteCover(intL[],intC[],int&m) {//寻找一个二分图覆盖 //L是输入顶点的标号,L[i]=1当且仅当i在Ａ中 //C是一个记录覆盖的输出数组 //如果图中不存在覆盖，则返回false //如果图中有一个覆盖，则返回true; //在m中返回覆盖的大小;在C[0:m-1]中返回覆盖 //插件结构 intSizeOfA=0; for(inti=1;i<=n;i++)//确定集合A的大小 if(L[i]==1)SizeOfA++; intSizeOfB=n-SizeOfA; CreateBins(SizeOfB,n); int*New=newint[n+1];//顶点i覆盖了Ｂ中New[i]个未被覆盖的顶点 bool*Change=newbool[n+1];//Change[i]为true当且仅当New[i]已改变 bool*Cov=newbool[n+1];//Cov[i]为true当且仅当顶点i被覆盖 InitializePos(); //初始化 for(i=1;i<=n;i++){ Cov[i]=Change[i]=false; if(L[i]==1){//i在A中 New[i]=Degree(i);//i覆盖了这么多 InsertBins(New[i],i);}} //构造覆盖 intcovered=0,//被覆盖的顶点 MaxBin=SizeOfB;//可能非空的最大箱子 m=0;//C的游标 while(MaxBin>0){//搜索所有箱子 //选择一个顶点 if(bin[MaxBin]){//箱子不空 intv=bin[MaxBin];//第一个顶点 C[m++]=v;//把v加入覆盖 //标记新覆盖的顶点 intj=Begin(v),k; while(j){ if(!Cov[j]){//j尚未被覆盖 covered++; //修改New k=Begin(j); while(k){ New[k]--;//j不计入在内 if(!Change[k]){ S.Add(k);//仅入栈一次 Change[k]=true;} k=NextVertex(j);} j=NextVertex(v);} //更新箱子 while(!S.IsEmpty()){ S.Delete(k); Change[k]=false; MoveBins(SizeOfB,New[k],k);} elseMaxBin--; DestroyBins(); delete[]New; delete[]Change; delete[]Cov; return(covered==SizeOfB); 程序13-4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组Cov和Change初始化为false，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。 为了构造覆盖，首先按SizeOfB递减至1的顺序检查双向链表。当发现一个非空的表时，就将其第一个顶点v加入到覆盖中，这种策略即为选择具有最大Neov[j]置为true，表示顶点j现在已被覆盖，同时将已被覆盖的B中的顶点数目加1。由于j是最近被覆w值的顶点。将所选择的顶点加入覆盖数组C并检查B中所有与它邻接的顶点。若顶点j与v邻接且还未被覆盖，则将C盖的，所有A中与j邻接的顶点的New值减1。下一个while循环降低这些New值并将New值被降低的顶点保存在一个栈中。当所有与顶点v邻接的顶点的Cov值更新完毕后，New值反映了A中每个顶点所能覆盖的新的顶点数，然而A中的顶点由于New值被更新，处于错误的双向链表中，下一个while循环则将这些顶点移到正确的表中。 1.3.5单源最短路径在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费）a[i][j]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b中，每条路径前面的数字为路径的长度。 利用E.Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说，Dijkstra的方法按路径长度顺序产生最短路径。 首先最初产生从s到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是Dijkstra算法。 可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图13-10中，b中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。 通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p[i]给出从s到达i的路径中顶点i前面的那个顶点。在本例中p[1:5]=[0,1,1,3,4]。从s到顶点i的路径可反向创建。从i出发按p[i],p[p[i]],p[p[p[i]]],.的顺序，直到到达顶点s或0。在本例中，如果从i=5开始，则顶点序列为p[i]=4,p[4]=3,p[3]=1=s，因此路径为1,3,4,5。 为能方便地按长度递增的顺序产生最短路径，定义d[i]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s到s的一条长度为0的路径，这时对于每个顶点i，d[i]等于a[s][i]（a是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。 综上所述，可以得到图13-11所示的伪代码，1)将与s邻接的所有顶点的p初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s到i的最短路径，即是由s到它自身那条路径再扩充一条边得到。当找到更短的路径时，p[i]值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新d的值。 1)初始化d[i]=a[s][i]（1≤i≤n）， 对于邻接于s的所有顶点i，置p[i]=s,对于其余的顶点置p[i]=0； 对于p[i]≠0的所有顶点建立L表。 2)若L为空，终止，否则转至3)。 3)从L中删除d值最小的顶点。 4)对于与i邻接的所有还未到达的顶点j，更新d[j]值为min{d[j],d[i]+a[i][j]}；若d[j]发生了变化且j还未 在L中，则置p[j]=1，并将j加入L，转至2。 图1-11最短路径算法的描述 1.数据结构的选择 程序13-5最短路径程序 voidAdjacencyWDigraph {//寻找从顶点s出发的最短路径,在d中返回最短距离 //在p中返回前继顶点 if(s<1||s>n)throwOutOfBounds(); Chain ChainIterator //初始化d,p,L for(inti=1;i<=n;i++){ d[i]=a[s][i]; if(d[i]==NoEdge)p[i]=0; else{p[i]=s; L.Insert(0,i);} //更新d,p while(!L.IsEmpty()){//寻找具有最小d的顶点v int*v=I.Initialize(L); int*w=I.Next(); while(w){ if(d[*w] w=I.Next();} //从L中删除通向顶点v的下一最短路径并更新d inti=*v; L.Delete(*v); for(intj=1;j<=n;j++){ if(a[i][j]!=NoEdge&&(!p[j]|| d[j]>d[i]+a[i][j])){ //减小d[j] d[j]=d[i]+a[i][j]; //将j加入L if(!p[j])L.Insert(0,j); p[j]=i;} 若NoEdge足够大，使得没有最短路径的长度大于或等于NoEdge，则最后一个for循环的if条件可简化为：if(d[j]>d[i]+a[i][j]))NoEdge的值应在能使d[j]+a[i][j]不会产生溢出的范围内。 2.复杂性分析 1.3.6最小耗费生成树在例1-2及1-3中已考察过这个问题。因为具有n个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是：Kruskal算法，Prim算法和Sollin算法。 1.Kruskal算法 (1)算法思想 Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 考察图1-12a中的网络。初始时没有任何边被选择。图13-12b显示了各节点的当前状态。边（1,6）是最先选入的边，它被加入到欲构建的生成树中，得到图13-12c。下一步选择边（3，4）并将其加入树中（如图13-12d所示）。然后考虑边(2，7)，将它加入树中并不会产生环路，于是便得到图13-12e。下一步考虑边（2，3）并将其加入树中（如图13-12f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（5，4）加入树中，得到的树如图13-12g所示。下一步考虑边（7，5），由于会产生环路，将其丢弃。最后考虑边（6，5）并将其加入树中，产生了一棵生成树，其耗费为99。图1-13给出了Kruskal算法的伪代码。 //在一个具有n个顶点的网络中找到一棵最小生成树 令T为所选边的集合，初始化T= 令E为网络中边的集合 while(E≠)&&(|T|≠n-1){ 令(u,v)为E中代价最小的边E=E-{(u,v)}//从E中删除边 if((u,v)加入T中不会产生环路)将（u,v）加入T if(|T|==n-1)T是最小耗费生成树 else网络不是互连的，不能找到生成树 图13-13Kruskao算法的伪代码 (2)正确性证明 利用前述装载问题所用的转化技术可以证明图13-13的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点：1)只要存在生成树，Kruskal算法总能产生一棵生成树；2)产生的生成树具有最小耗费。令G为任意加权无向图（即G是一个无向网络）。从12.11.3节可知当且仅当一个无向图连通时它有生成树。而且在Kruskal算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E=和|T| 现在来证明所建立的生成树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+-{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)数据结构的选择及复杂性分析 对集合T所执行的唯一操作是向T中添加一条新边。T可用数组t来实现。添加操作在数组 (4)实现 利用上述数据结构，图1-13可用C++代码来实现。首先定义EdgeNode类（见程序13-6)，它是最小堆的元素及生成树数组t的数据类型。 程序13-6Kruskal算法所需要的数据类型 template classEdgeNode{ public: operatorT()const{returnweight;} private: Tweight;//边的高度 intu,v;//边的端点 }; 为了更简单地使用8.10.2节的查找和合并策略，定义了UnionFind类，它的构造函数是程序8-16的初始化函数，Union是程序8-16的加权合并函数，Find是程序8-17的路径压缩搜索函数。 为了编写与网络描述无关的代码，还定义了一个新的类UNetWork，它包含了应用于无向网络的所有函数。这个类与Undirected类的差别在于Undirected类中的函数不要求加权边，而UNetWork要求边必须带有权值。UNetWork中的成员需要利用Network类中定义的诸如Begin和NextVertex的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起构成了WNetwork类（见程序13-7）。 程序13-7WNetwork类 classWNetwork:virtualpublicNetwork { virtualvoidFirst(inti,int&j,T&c)=0; virtualvoidNext(inti,int&j,T&c)=0; 象Begin和NextVertex一样，可在AdjacencyWDigraph及LinkedWDigraph类中加入函数First与Next。现在AdjacencyWDigraph及LinkedWDigraph类都需要从WNetWork中派生而来。由于AdjacencyWGraph类和LinkedWGraph类需要访问UNetwork的成员，所以这两个类还必须从UNetWork中派生而来。UNetWork::Kruskal的代码见程序13-8，它要求将Edges()定义为NetWork类的虚成员，并且把UNetWork定义为EdgeNode的友元）。如果没有生成树，函数返回false，否则返回true。注意当返回true时，在数组t中返回最小耗费生成树。 程序13-8Kruskal算法的C++代码 boolUNetwork::Kruskal(EdgeNodet[]) {//使用Kruskal算法寻找最小耗费生成树 //如果不连通则返回false //如果连通，则在t[0:n-2]中返回最小生成树 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(i E[++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);} H.Deactivate(); return(k==n-1); 2.Prim算法 与Kruskal算法类似，Prim算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准则是：从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所有步骤中选择的边形成一棵树。相反，在Kruskal算法中所有入选的边集合最终形成一个森林。 Prim算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。然后往T中加入一条代价最小的边（u,v）使Tè{(u,v)}仍是一棵树，这种加边的步骤反复循环直到T中包含n-1条边。注意对于边（u,v），u、v中正好有一个顶点位于T中。Prim算法的伪代码如图1-14所示。在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。图1-15显示了对图1-12a使用Prim算法的过程。把图1-14的伪代码细化为C++程序及其正确性的证明留作练习（练习31）。 //假设网络中至少具有一个顶点 设T为所选择的边的集合，初始化T= 设TV为已在树中的顶点的集合，置TV={1} 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最小生成树算法 3.Sollin算法 Sollin算法每步选择若干条边。在每步开始时，所选择的边及图中的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。Sollin算法的C++程序实现及其正确性证明留作练习（练习32)。