常用算法大全－贪婪算法

ゝ一世哀愁。 2021-11-16 12:38 444阅读 0赞

原地址: [http://www.cnblogs.com/tuyile006/archive/2007/06/07/774734.html][http_www.cnblogs.com_tuyile006_archive_2007_06_07_774734.html]

本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。

1.1 最优化问题

本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合限制条件的问题求解方案称为可行解（ feasible solution），使优化函数取得最佳值的可行解称为最优解（optimal solution）。

例1-1 \[ 渴婴问题\] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i 种饮料，对它作出相对评价，将一个数值si 作为满意度赋予第i 种饮料。

通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量（以盎司为单位），而此婴儿需要t 盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？

设各种饮料的满意度已知。令xi 为婴儿将要饮用的第i 种饮料的量，则需要解决的问题是：

找到一组实数xi（1≤i≤n），使n ?i = 1si xi 最大，并满足：n ?i=1xi =t 及0≤xi≤ai 。

需要指出的是：如果n ?i = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使婴儿解渴。

对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述：

输入：n，t，si ，ai（其中1≤i≤n，n 为整数，t、si 、ai 为正实数）。

输出：实数xi（1≤i≤n），使n ?i= 1si xi 最大且n ?i=1xi =t（0≤xi≤ai）。如果n ?i = 1ai <t，则输出适当的错误信息。

在这个问题中，限制条件是n ?i= 1xi =t 且0≤xi≤ai，1≤i≤n。而优化函数是n ?i= 1si xi 。任何满足限制条件的一组实数xi 都是可行解，而使n ?i= 1si xi 最大的可行解是最优解。

例1-2 \[装载问题\] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i 个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。

这个问题可以作为最优化问题进行描述：设存在一组变量xi ，其可能取值为0或1。如xi 为0，则货箱i 将不被装上船；如xi 为1，则货箱i 将被装上船。我们的目的是找到一组xi ，使它满足限制条件n ?i = 1wi xi ≤c 且x i ? \{0, 1\}, 1 ≤i≤n。相应的优化函数是n ?i= 1xi 。

满足限制条件的每一组xi 都是一个可行解，能使n ?i= 1xi 取得最大值的方案是最优解。

例1-3 \[最小代价通讯网络\] 城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。

在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。    
1.2 算法思想

在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。

例1-4 \[找零钱\] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。

假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。

贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。

例1-5 \[机器调度\] 现有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi ，si < fi 。\[si , fi \] 为处理任务i 的时间范围。两个任务i，j 重指两个任务的时间范围区间有重叠，而并非是指i，j 的起点或终点重合。例如：区间\[ 1，4 \]与区间\[ 2，4 \]重叠，而与区间\[ 4，7 \]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。

假设有n= 7件任务，标号为a 到g。它们的开始与完成时间如图13-1a 所示。若将任务a分给机器M1，任务b 分给机器M2，. . .，任务g 分给机器M7，这种分配是可行的分配，共使用了七台机器。但它不是最优分配，因为有其他分配方案可使利用的机器数目更少，例如：可以将任务a、b、d分配给同一台机器，则机器的数目降为五台。

一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务，且按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分给旧的机器。否则，将任务分配给一台新的机器。 根据例子中的数据，贪婪算法共分为n = 7步，任务分配的顺序为a、f、b、c、g、e、d。第一步没有旧机器，因此将a 分配给一台新机器（比如M1）。这台机器在0到2时刻处于忙状态。在第二步，考虑任务f。由于当f 启动时旧机器仍处于忙状态，因此将f 分配给一台新机器(设为M2 )。第三步考虑任务b, 由于旧机器M1在Sb = 3时刻已处于闲状态，因此将b分配给M1执行，M1下一次可用时刻变成fb = 7，M2的可用时刻变成ff = 5。第四步，考虑任务c。由于没有旧机器在Sc = 4时刻可用，因此将c 分配给一台新机器（M3），这台机器下一次可用时间为fc = 7。第五步考虑任务g，将其分配给机器M2，第六步将任务e 分配给机器M1, 最后在第七步，任务2分配给机器M3。（注意：任务d 也可分配给机器M2）。

上述贪婪算法能导致最优机器分配的证明留作练习（练习7）。可按如下方式实现一个复杂性为O (nl o gn)的贪婪算法：首先采用一个复杂性为O (nl o gn)的排序算法（如堆排序）按Si 的递增次序排列各个任务，然后使用一个关于旧机器可用时间的最小堆。

例1-6 \[最短路径\] 给出一个有向网络，路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点s 到达目的顶点d 的最短路径。

贪婪算法分步构造这条路径，每一步在路径中加入一个顶点。假设当前路径已到达顶点q，

且顶点q 并不是目的顶点d。加入下一个顶点所采用的贪婪准则为：选择离q 最近且目前不在路径中的顶点。

这种贪婪算法并不一定能获得最短路径。例如，假设在图1 3 - 2中希望构造从顶点1到顶点5的最短路径，利用上述贪婪算法，从顶点1开始并寻找目前不在路径中的离顶点1最近的顶点。到达顶点3，长度仅为2个单位，从顶点3可以到达的最近顶点为4，从顶点4到达顶点2，最后到达目的顶点5。所建立的路径为1 , 3 , 4 , 2 , 5，其长度为1 0。这条路径并不是有向图中从1到5的最短路径。事实上，有几条更短的路径存在，例如路径1，4，5的长度为6。

根据上面三个例子，回想一下前几章所考察的一些应用，其中有几种算法也是贪婪算法。例如，霍夫曼树算法，利用n- 1步来建立最小加权外部路径的二叉树，每一步都将两棵二叉树合并为一棵，算法中所使用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。L P T调度规则也是一种贪婪算法，它用n 步来调度n 个作业。首先将作业按时间长短排序，然后在每一步中为一个任务分配一台机器。选择机器所利用的贪婪准则为：使目前的调度时间最短。将新作业调度到最先完成的机器上（即最先空闲的机器）。

注意到在机器调度问题中，贪婪算法并不能保证最优，然而，那是一种直觉的倾向且一般情况下结果总是非常接近最优值。它利用的规则就是在实际环境中希望人工机器调度所采用的规则。算法并不保证得到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（ h e u r i s t i c s )。因此L P T方法是一种启发式机器调度方法。定理9 - 2陈述了L P T调度的完成时间与最佳调度的完成时间之间的关系，因此L P T启发式方法具有限定性

能（ bounded performance ）。具有限定性能的启发式方法称为近似算法（ a p p r o x i m a t i o na l g o r i t h m）。

本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。

1.3.1 货箱装船

这个问题来自例1 - 2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。   
例1-7 假设n =8, \[w1 , ... w8 \]=\[100,200,50,90,150,50,20,80\], c= 4 0 0。利用贪婪算法时，所考察货箱的顺序为7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱7 , 3 , 6 , 8 , 4 , 1的总重量为3 9 0个单位且已被装载，剩下的装载能力为1 0个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到\[x1 , ..., x8 \] = \[ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 \]且?xi = 6。

定理1-1 利用贪婪算法能产生最佳装载。

证明可以采用如下方式来证明贪婪算法的最优性：令x = \[x1 , ..., xn \]为用贪婪算法获得的解，令y =\[ y1 , ..., yn \]为任意一个可行解，只需证明n ?i= 1xi ≥n ?i= 1yi 。不失一般性，可以假设货箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分几步将y 转化为x，转换过程中每一步都产生一个可行的新y，且n ?i = 1yi 大于等于未转化前的值，最后便可证明n ?i = 1xi ≥n ?j = 1yi 。

根据贪婪算法的工作过程，可知在\[0, n\] 的范围内有一个k，使得xi =1, i≤k且xi =0, i>k。寻找\[ 1 ,n\]范围内最小的整数j，使得xj≠yj 。若没有这样的j 存在，则n ?i= 1xi =n ?i = 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。

经过数次这种转化，可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1，因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序（见3 . 5节间接寻址的定义），随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)（也可利用9 . 5 . 1节的堆排序及第2章的归并排序），算法其余部分所需时间为O (n)，因此程序1 3 - 1的总的复杂性为O (nl o gn)。

程序13-1 货箱装船

template<class T>

void ContainerLoading(int x\[\], T w\[\], T c, int n)

\{// 货箱装船问题的贪婪算法

// x\[i\] = 1 当且仅当货箱i被装载， 1<=i<=n

// c是船的容量, w 是货箱的重量

// 对重量按间接寻址方式排序

// t 是间接寻址表

int \*t = new int \[n+1\];

I n d i r e c t S o r t ( w, t, n);

// 此时, w\[t\[i\]\] <= w\[t\[i+1\]\], 1<=i<n

// 初始化x

for (int i = 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.2 0/1背包问题  
在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。约束条件为n ?i =1wi xi≤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 = 1 0 5。当利用价值贪婪准则时，获得的解为x= \[ 1 , 0 , 0 \]，这种方案的总价值为2 0。而最优解为\[ 0 , 1 , 1 \]，其总价值为3 0。

另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=\[10,20\], p=\[5,100\], c= 2 5。当利用重量贪婪策略时，获得的解为x =\[1,0\], 比最优解\[ 0 , 1 \]要差。

还可以利用另一方案，价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可

装入包的pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=\[20,15,15\], p=\[40,25,25\], c=30 时的最优解。

我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中，用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %，所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问，是否存在一个x (x<1 0 0 )，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n =2, w = \[ 1 ,y\], p= \[ 1 0 , 9y\], 和c= y。贪婪算法结果为x=\[1,0\], 这种方案的值为1 0。对于y≥1 0 / 9，最优解的值为9 y。因此，贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y\* 1 0 0 ) %，对于大的y，这个值趋近于1 0 0 %。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x% (x<100) 之内。首先将最多k 件物品放入背包，如果这k 件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。

例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 \]。此解获得的价值为1 6。

现在考虑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 \]，获得的价值为1 8。若从子集\{ 4 \}开始，产生的解为x = \[ 1 , 0 , 0 , 1 \]，获得的价值为1 9。考虑子集大小为0和1时获得的最优解为\[ 1 , 0 , 0 , 1 \]。这个解是通过k= 1的贪婪启发式算法得到的。

若k= 2，除了考虑k< 2的子集，还必需考虑子集\{ 1 , 2 \} , \{ 1 , 3 \} , \{ 1 , 4 \} , \{ 2 , 3 \} , \{ 2 , 4 \}和\{ 3 , 4 \}。首先从最后一个子集开始，它是不可行的，故将其抛弃，剩下的子集经求解分别得到如下结果：\[ 1 , 1 , 0 , 0 \] , \[ 1 , 0 , 1 , 0 \] , \[ 1 , 0 , 0 , 1 \] , \[ 0 , 1 , 1 , 0 \]和\[ 0 , 1 , 0 , 1 \]，这些结果中最后一个价值为2 3，它的值比k= 0和k= 1时获得的解要高，这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法（k - o p t i m a l）。也就是，若从答案中取出k 件物品，并放入另外k 件，获得的结果不会比原来的好，而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当k= 1时，保证最终结果在最佳值的5 0 %以内；当k= 2时，则在3 3 . 3 3 %以内等等，这种启发式方法的执行时间随k 的增大而增加，需要测试的子集数目为O (nk )，每一个子集所需时间为O (n)，因此当k >0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。

1.3.3 拓扑排序  
一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, 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）已暗示了这种关系。

在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边（ i, j）表示在装配序列中任务i 在任务j 的前面，具有这种性质的序列称为拓扑序列（topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序（topological sorting）。图1 - 4的任务有向图有多种拓扑序列，其中的三种为1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（ 3 , 4），这种序列与边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点：从剩下的顶点中，选择顶点w，使得w 不存在这样的入边（ v,w），其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则（即有向图中存在边（ v,w）且v 不在已构造的序列中），则无法完成拓扑排序，因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。

现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V = 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2 5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V

得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。

1. 贪婪算法的正确性

为保证贪婪算法算的正确性，需要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若

算法没有失败，V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。

定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。

证明注意到当失败时| V |<n, 且没有候选顶点能加入V中，因此至少有一个顶点q1 不在V中，有向图中必包含边（ q2 , q1）且q2 不在V中，否则， q1 是可加入V的候选顶点。同样，必有边（q3 , q2）使得q3 不在V中，若q3 = q1 则q1 q2 q3 是有向图中的一个环路；若q3 ≠q1，则必存在q4 使（q4 , q3）是有向图的边且q4 不在V中，否则，q3 便是V的一个候选顶点。若q4 为q1 , q2 , q3 中的任何一个，则又可知有向图含有环，因为有向图具有有限个顶点数n，继续利用上述方法，最后总能找到一个环路。

2. 数据结构的选择

为将图1 - 5用C + +代码来实现，必须考虑序列V的描述方法，以及如何找出可加入V的候选顶点。一种高效的实现方法是将序列V用一维数组v 来描述的，用一个栈来保存可加入V的候选顶点。另有一个一维数组I n D e g r e e，I n D e g r e e\[ j \]表示与顶点j相连的节点i 的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（ i, j）。当I n D e g r e e\[ j \]变为0时表示j 成为一个候选节点。序列V初始时为空。I n D e g r e e\[ j \]为顶点j 的入度。每次向V中加入一个顶点时，所有与新加入顶点邻接的顶点j，其I n D e g r e e\[ j \]减1。对于有向图1 - 4，开始时I n D e g r e e \[ 1 : 6 \] = \[ 0 , 0 , 1 , 3 , 1 , 3 \]。由于顶点1和2的I n D e g r e e值为0，因此它们是可加入V的候选顶点，由此，顶点1和2首先入栈。每一步，从栈中取出一个顶点将其加入V，同时减去与其邻接的顶点的I n D e g r e e值。若在第一步时从栈中取出顶点2并将其加入V，便得到了v \[ 0 \] = 2，和I n D e g r e e \[ 1 : 6 \] = \[ 0 , 0 , 1 , 2 , 0 , 3 \]。由于I n D e g r e e \[ 5 \]刚刚变为0，因此将顶点5入栈。

程序1 3 - 2给出了相应的C + +代码，这个代码被定义为N e t w o r k的一个成员函数。而且，它对于有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针对有向图来定义的。为解决这个问题，利用同样的模板来定义成员函数AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。这些函数可重载N e t w o r k中的函数并可输出错误信息。如果找到拓扑序列，则Topological 函数返回t r u e；若输入的有向图无拓扑序列则返回f a l s e。当找到拓扑序列时，将其返回到v \[ 0 :n- 1 \]中。

3. Network:Topological 的复杂性

第一和第三个f o r循环的时间开销为(n )。若使用（耗费）邻接矩阵,则第二个for 循环所用的时间为(n2 )；若使用邻接链表,则所用时间为(n+e)。在两个嵌套的while 循环中，外层循环需执行n次，每次将顶点w 加入到v 中，并初始化内层while 循环。使用邻接矩阵时，内层w h i l e循环对于每个顶点w 需花费(n)的时间；若利用邻接链表，则这个循环需花费dwout 的时间，因此，内层while 循环的时间开销为(n2 )或(n+e)。所以，若利用邻接矩阵，程序1 3 - 2的时间复杂性为(n2 )，若利用邻接链表则为(n+e)。

程序13-2 拓扑排序

bool Network::Topological(int v\[\])

\{// 计算有向图中顶点的拓扑次序

// 如果找到了一个拓扑次序，则返回t r u e，此时，在v \[ 0 : n - 1 \]中记录拓扑次序

// 如果不存在拓扑次序，则返回f a l s e

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

// 计算入度

int \*InDegree = new int \[n+1\];

InitializePos(); // 图遍历器数组

for (int i = 1; i <= n; i++) // 初始化

InDegree\[i\] = 0;

for (i = 1; i <= n; i++) \{// 从i 出发的边

int u = Begin(i);

while (u) \{

I n D e g r e e \[ u \] + + ;

u = NextVe r t e x ( i ) ; \}

// 把入度为０的顶点压入堆栈

LinkedStack<int> S;

for (i = 1; i <= n; i++)

if (!InDegree\[i\]) S.Add(i);

// 产生拓扑次序

i = 0; // 数组v 的游标

while (!S.IsEmpty()) \{// 从堆栈中选择

int w; // 下一个顶点

S . D e l e t e ( w ) ;

v\[i++\] = w;

int u = Begin(w);

while (u) \{// 修改入度

I n D e g r e e \[ u \] - - ;

if (!InDegree\[u\]) S.Add(u);

u = NextVe r t e x ( w ) ; \}

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

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所示的具有1 7个顶点的二分图，A=\{1, 2, 3, 16, 17\}和B=\{4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15\}，子集A' = \{ 1 , 1 6 , 1 7 \}是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。

二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k 个集合S= \{S1 , S2 ,., Sk \}，每个集合Si 中的元素均是全集U中的成员。当且仅当èi S'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，1 3 \}，S2 = \{ 4，5，6，8 \}，S3 = \{ 8，1 0，1 2，1 4，1 5 \}，S4 = \{ 5，6，8，1 2，1 4，1 5 \}，S5 = \{ 4，9，1 0，11 \}。S ' = \{S1，S4，S5 \}是一个大小为3的覆盖，没有更小的覆盖， S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。

集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。

例1-12 考察图1 - 6所示的二分图，初始化A' = 且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为\{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 \}，未覆盖的顶点为\{ 4 , 7 , 9 , 1 0 , 11 , 1 3 \}。顶点1能覆盖其中四个顶点（ \{ 4 , 7 , 9 , 1 3 \}），顶点2 覆盖一个( \{ 4 \} )，顶点3覆盖一个（\{ 1 0 \}），顶点1 6覆盖零个，顶点1 7覆盖四个\{ 4 , 9 , 1 0 , 11 \}。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点\{ 1 0 , 11\} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A' = \{ 1 6 , 1 , 1 7 \}。

图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。

1. 数据结构的选取及复杂性分析

为实现图13 - 7的算法，需要选择A' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A' 仅使用加法运算，则可用一维整型数组C来描述A '，用m 来记录A' 中元素个数。将A' 中的成员记录在C\[ 0 :m-1\] 中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi 值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。

例1-13 考察图1 - 6，初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。假设在例1 - 1 2中，第一步选择顶点1 6，为更新N e wi 的值检查B中所有最近被覆盖的顶点，这些顶点为5 , 6 , 8 , 1 2 , 1 4和1 5。当检查顶点5时，将顶点2和1 6的N e wi 值分别减1，因为顶点5不再是被顶点2和1 6覆盖的未覆盖节点；当检查顶点6时，顶点1 , 2 ,和1 6的相应值分别减1；同样，检查顶点8时，1，2，3和1 6的值分别减1；当检查完所有最近被覆盖的顶点，得到的N e wi 值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和1 3；检查顶点4时，N e w1 , N e w2, 和N e w1 7 的值减1；检查顶点7时，N e w1 的值减1，因为顶点1是覆盖7的唯一顶点。

为了实现顶点选取的过程，需要知道N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，N e w是一个整型数组，New\[i\] 即等于N e wi，且c o v为一个布尔数组。若顶点i未被覆盖则c o v \[ i \]等于f a l s e，否则c o v \[ i \]为t r u e。现将图1 - 7的伪代码进行细化得到图1 - 8。

m=0; //当前覆盖的大小

对于A中的所有i，New\[i\]=Degree\[i\]

对于B中的所有i，C o v \[ i \] = f a l s e

while (对于A中的某些i,New\[i\]>0) \{

设v是具有最大的N e w \[ i \]的顶点；

C \[ m + + \] = v ;

for ( 所有邻接于v的顶点j) \{

if (!Cov\[j\]) \{

Cov\[j\]= true;

对于所有邻接于j的顶点，使其N e w \[ k \]减1

\} \} \}

if (有些顶点未被覆盖) 失败

else 找到一个覆盖

图1-8 图1-7的细化

更新N e w的时间为O (e)，其中e 为二分图中边的数目。若使用邻接矩阵，则需花(n2 ) 的时间来寻找图中的边，若用邻接链表，则需(n+e) 的时间。实际更新时间根据描述方法的不同为O (n2 ) 或O (n+e)。逐步选择顶点所需时间为(S i z e O f A)，其中S i z e O f A=| A |。因为A的所有顶点都有可能被选择，因此所需步骤数为O ( S i z e O f A )，覆盖算法总的复杂性为O ( S i z e O f A 2+n2) = O ( n2)或O (S i z e Of A2+n + e)。

2. 降低复杂性

通过使用有序数组N e wi、最大堆或最大选择树（max selection tree）可将每步选取顶点v的复杂性降为( 1 )。但利用有序数组，在每步的最后需对N e wi 值进行重新排序。若使用箱子排序，则这种排序所需时间为(S i z e O f B ) ( S i z e O fB =|B| ) （见3 . 8 . 1节箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序数组并不总能提高性能。

如果利用最大堆，则每一步都需要重建堆来记录N e w值的变化，可以在每次N e w值减1时进行重建。这种减法操作可引起被减的N e w值最多在堆中向下移一层，因此这种重建对于每次N e w值减1需( 1 )的时间，总共的减操作数目为O (e)。因此在算法的所有步骤中，维持最大堆仅需O (e)的时间，因而利用最大堆时覆盖算法的总复杂性为O (n2 )或O (n+e)。

若利用最大选择树，每次更新N e w值时需要重建选择树，所需时间为(log S i z e O f A)。重建的最好时机是在每步结束时，而不是在每次N e w值减1时，需要重建的次数为O (e)，因此总的重建时间为O (e log S i z e OfA)，这个时间比最大堆的重建时间长一些。然而，通过维持具有相同N e w值的顶点箱子，也可获得和利用最大堆时相同的时间限制。由于N e w的取值范围为0到S i z e O f B，需要S i z e O f B+ 1个箱子，箱子i 是一个双向链表，链接所有N e w值为i 的顶点。在某一步结束时，假如N e w \[ 6 \]从1 2变到4，则需要将它从第1 2个箱子移到第4个箱子。利用模拟指针及一个节点数组n o d e（其中n o d e \[ i \]代表顶点i，n o d e \[ i \] . l e f t和n o d e \[ i \] . r i g h t为双向链表指针），可将顶点6从第1 2个箱子移到第4个箱子，从第1 2个箱子中删除n o d e \[ 0 \]并将其插入第4个箱子。利用这种箱子模式，可得覆盖启发式算法的复杂性为O (n2 )或O(n+e)。（取决于利用邻接矩阵还是线性表来描述图）。

3. 双向链接箱子的实现

为了实现上述双向链接箱子，图1 - 9定义了类U n d i r e c t e d的私有成员。N o d e Ty p e是一个具有私有整型成员l e f t和r i g h t的类，它的数据类型是双向链表节点，程序1 3 - 3给出了U n d i r e c t e d的私有成员的代码。

void CreateBins (int b, int n)

创建b个空箱子和n个节点

void DestroyBins() \{ delete \[\] node;

delete \[\] bin;\}

void InsertBins(int b, int v)

在箱子b中添加顶点v

void MoveBins(int bMax, int ToBin, int v)

从当前箱子中移动顶点v到箱子To B i n

int \*bin;

b i n \[ i \]指向代表该箱子的双向链表的首节点

N o d e Type \*node;

n o d e \[ i \]代表存储顶点i的节点

图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员

程序13-3 箱子函数的定义

void Undirected::CreateBins(int b, int n)

\{// 创建b个空箱子和n个节点

node = new NodeType \[n+1\];

bin = new int \[b+1\];

// 将箱子置空

for (int i = 1; i <= b; i++)

bin\[i\] = 0;

void Undirected::InsertBins(int b, int v)

\{// 若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;

void Undirected::MoveBins(int bMax, int ToBin, int v)

\{// 将顶点v 从其当前所在箱子移动到To B i n .

// v的左、右节点

int l = node\[v\].left;

int r = node\[v\].right;

// 从当前箱子中删除

if (r) node\[r\].left = node\[v\].left;

if (l > bMax || bin\[l\] != v) // 不是最左节点

node\[l\].right = r;

else bin\[l\] = r; // 箱子l的最左边

// 添加到箱子To B i n

I n s e r t B i n s ( ToBin, v);

函数C r e a t e B i n s动态分配两个数组： n o d e和b i n，n o d e \[i \]表示顶点i, bin\[i \]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果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\] 的右指针被置为b i n \[ b \]，其值可能为0或指向上一个首节点的指针。最后， b i n \[ b \]被更新为指向表中新的第一个节点。MoveBins 将顶点v 从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n\[ j \]都有：如j>bMa x，则b i n \[ j \]为空。代码首先确定n o d e \[ v \]在当前双向链表中的左右节点，接着从双链表中取出n o d e \[ v \]，并利用I n s e r t B i n s函数将其重新插入到b i n \[ To B i n \]中。

4. Undirected::BipartiteCover的实现

函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L \[i \] = 1表示顶点i在集合A中，L\[ i \] = 2则表示顶点在B中。函数有两个输出参数： C和m，m为所建立的覆盖的大小， C \[ 0 , m - 1 \]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回f a l s e；否则返回t r u e。完整的代码见程序1 3 - 4。

程序13-4 构造贪婪覆盖

bool Undirected::BipartiteCover(int L\[\], int C\[\], int& m)

\{// 寻找一个二分图覆盖

// L 是输入顶点的标号, L\[i\] = 1 当且仅当i 在Ａ中

// C 是一个记录覆盖的输出数组

// 如果图中不存在覆盖，则返回f a l s e

// 如果图中有一个覆盖，则返回t r u e ;

// 在m中返回覆盖的大小; 在C \[ 0 : m - 1 \]中返回覆盖

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

// 插件结构

int SizeOfA = 0;

for (int i = 1; i <= n; i++) // 确定集合A的大小

if (L\[i\] == 1) SizeOfA++;

int SizeOfB = n - SizeOfA;

CreateBins(SizeOfB, n);

int \*New = new int \[n+1\]; / /顶点i覆盖了Ｂ中N e w \[ i \]个未被覆盖的顶点

bool \*Change = new bool \[n+1\]; // Change\[i\]为t r u e当且仅当New\[i\] 已改变

bool \*Cov = new bool \[n+1\]; // Cov\[i\] 为true 当且仅当顶点i 被覆盖

I n i t i a l i z e P o s ( ) ;

LinkedStack<int> S;

// 初始化

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);\}\}

// 构造覆盖

int covered = 0, // 被覆盖的顶点

MaxBin = SizeOfB; // 可能非空的最大箱子

m = 0; // C的游标

while (MaxBin > 0) \{ // 搜索所有箱子

// 选择一个顶点

if (bin\[MaxBin\]) \{ // 箱子不空

int v = bin\[MaxBin\]; // 第一个顶点

C\[m++\] = v; // 把v 加入覆盖

// 标记新覆盖的顶点

int j = Begin(v), k;

while (j) \{

if (!Cov\[j\]) \{// j尚未被覆盖

Cov\[j\] = true;

c o v e r e d + + ;

// 修改N e w

k = Begin(j);

while (k) \{

New\[k\]--; // j 不计入在内

if (!Change\[k\]) \{

S.Add(k); // 仅入栈一次

Change\[k\] = true;\}

k = NextVe r t e x ( j ) ; \}

j = NextVe r t e x ( v ) ; \}

// 更新箱子

while (!S.IsEmpty()) \{

S . D e l e t e ( k ) ;

Change\[k\] = false;

MoveBins(SizeOfB, New\[k\], k);\}

else MaxBin--;

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

D e s t r o y B i n s ( ) ;

delete \[\] New;

delete \[\] Change;

delete \[\] Cov;

return (covered == SizeOfB);

程序1 3 - 4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组C o v和C h a n g e初始化为f a l s e，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。

为了构造覆盖，首先按SizeOfB 递减至1的顺序检查双向链表。当发现一个非空的表时，就将其第一个顶点v 加入到覆盖中，这种策略即为选择具有最大Ne o v \[ j \]置为t r u e，表示顶点j 现在已被覆盖，同时将已被覆盖的B中的顶点数目加1。由于j 是最近被覆w 值的顶点。将所选择的顶点加入覆盖数组C并检查B中所有与它邻接的顶点。若顶点j 与v 邻接且还未被覆盖，则将C盖的，所有A中与j 邻接的顶点的New 值减1。下一个while 循环降低这些New 值并将New 值被降低的顶点保存在一个栈中。当所有与顶点v邻接的顶点的Cov 值更新完毕后，N e w值反映了A中每个顶点所能覆盖的新的顶点数，然而A中的顶点由于New 值被更新，处于错误的双向链表中，下一个while 循环则将这些顶点移到正确的表中。

1.3.5 单源最短路径  
在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费） a \[i \]\[ j \]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s 为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。

利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a的方法按路径长度顺序产生最短路径。

首先最初产生从s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是D i j k s t r a算法。

可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1 3 - 1 0中，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值可能会发生变化。

综上所述，可以得到图1 3 - 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 \]值为m i n\{d\[ j \], d\[i \] +a\[i \]\[ j \] \}；若d\[ j \]发生了变化且j 还未

在L中，则置p\[ j \] = 1，并将j 加入L，转至2。

图1 - 11 最短路径算法的描述

1. 数据结构的选择

我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d 值最小的顶点。如果L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n )。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d 值，所以在4) 中可能需要改变一些d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为O ( n2 l o g n )。

若L用无序的链表来维护，则3) 与4) 花费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n )的时间，每次减操作需( 1 )的时间（需要减去d\[j\] 的值，但链表不用改变）。利用无序链表将图1 - 11的伪代码细化为程序1 3 - 5，其中使用了C h a i n (见程序3 - 8 )和C h a i n I t e r a t o r类（见程序3 - 1 8）。

程序13-5 最短路径程序

template<class T>

void AdjacencyWDigraph<T>::ShortestPaths(int s, T d\[\], int p\[\])

\{// 寻找从顶点s出发的最短路径, 在d中返回最短距离

// 在p中返回前继顶点

if (s < 1 || s > n) throw OutOfBounds();

Chain<int> L; // 路径可到达顶点的列表

ChainIterator<int> I;

// 初始化d, p, L

for (int i = 1; i <= n; i++)\{

d\[i\] = a\[s\]\[i\];

if (d\[i\] == NoEdge) p\[i\] = 0;

else \{p\[i\] = s;

L . I n s e r t ( 0 , i ) ; \}

// 更新d, p

while (!L.IsEmpty()) \{// 寻找具有最小d的顶点v

int \*v = I.Initialize(L);

int \*w = I.Next();

while (w) \{

if (d\[\*w\] < d\[\*v\]) v = w;

w = I.Next();\}

// 从L中删除通向顶点v的下一最短路径并更新d

int i = \*v;

L . D e l e t e ( \* v ) ;

for (int j = 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;\}

若N o E d g e足够大，使得没有最短路径的长度大于或等于N o E d g e，则最后一个for 循环的i f条件可简化为：if (d\[j\] > d\[i\] + a\[i\]\[j\])) NoEdge 的值应在能使d\[j\]+a\[i\]\[j\] 不会产生溢出的范围内。

2. 复杂性分析

程序1 3 - 5的复杂性是O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有可能在最短路径中。因此这种算法的最小可能时间为O ( e )。由于使用耗费邻接矩阵来描述图，仅决定哪条边在有向图中就需O ( n2 )的时间。因此，采用这种描述方法的算法需花费O ( n2 )的时间。不过程序1 3 - 5作了优化（常数因子级）。即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e )（因为只有与i 邻接的顶点的d 值改变）。从L中选择及删除最小距离的顶点所需总时间仍然是O( n2 )。

1.3.6 最小耗费生成树  
在例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算法的伪代码

(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+ -\{ 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 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 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

bool UNetwork::Kruskal(EdgeNode 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 \*E = new EdgeNode \[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 > H(1);

H.Initialize(E, e, e);

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

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

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

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

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

EdgeNode 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）为最小代价边，其中u T V, v T V

i f（没有这种边） b re a k

E=E- \{ (u,v) \} / /从E中删除此边

在T中加入边（ u , v）

if (| T | = =n- 1 ) T是一棵最小生成树

else 网络是不连通的，没有最小生成树

图13-14 Prim最小生成树算法

如果根据每个不在T V中的顶点v 选择一个顶点n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v) )的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间复杂性为O (n2 )。下一条添加到T中的边是这样的边：其cost (v, near (v)) 最小，且v T V。

3. Sollin算法

S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。

图1 - 6给出了初始状态为图1-12a 时，使用S o l l i n算法的步骤。初始入选边数为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 )，将这些边加入入选边的集合后所得到的结果如图1 3 - 1 6 a所示。下一步具有顶点集\{ 1 , 6 \}的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形成一棵生成树，构建好的生成树见图1 3 - 6 b。S o l l i n算法的C + +程序实现及其正确性证明留作练习（练习3 2 )。

\---------------------------------------------------------------------

转载于:https://www.cnblogs.com/hnrainll/archive/2011/04/29/2032733.html

[http_www.cnblogs.com_tuyile006_archive_2007_06_07_774734.html]: http://www.cnblogs.com/tuyile006/archive/2007/06/07/774734.html