第3章 算法之贪心算法

1、第三章 算法之贪心算法本章主要知识点（46学时）： 3.1 活动安排问题 3.2 贪心算法的基本要素 3.3 最优装载 3.4 哈夫曼编码 3.5 单源最短路径 3.6 最小生成树 3.7 多机调度问题引言【找零钱问题】希望用数目最少的硬币找零假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。 假设需要找67美分，25+25+10+5+1+1，共6枚。假设提供了数目不限的面值为1 1美分、5美分及1美分的硬币？找零15美分 11+1+1+1+1，共5枚（贪心算法） 5+5+5，共3枚（非贪心算法）在一些情况下，即使贪心算法不能得到在一些情况下，即使贪心算法不能得到整体最

2、优解整体最优解，其，其最终结果却是最终结果却是最优解的很好近似最优解的很好近似。引言贪心算法：总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。引言贪心法存在的问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。 3.1 活动安排问题【活动安排问题】就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用

3、某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sjfi时，活动i与活动j相容。复杂性分析由于输入的活动以其完成时间的升序排列，所以算法greedySelector每次总是选择最早完成时间的相容活动加

4、入集合A中。为未安排活动留下尽可能多的时间。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的活动。一个实例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：说明若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。贪心算法描述public static int greedySelector(int s, int

5、 f, boolean a) int n=s.length-1;a1=true; /选择最早结束活动选择最早结束活动int j=1;/j表示已安排活动编号表示已安排活动编号int count=1;/已安排活动数已安排活动数for (int i=2;i=fj) ai=true;j=i;count+; else ai=false;return count;各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 复杂性分析算法greedySelector的效率极高。当输入的活动已按结束时间的升序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动

6、未按非减序排列，可以用O(nlogn)的时间重排。3.2 贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质： 贪心选择性质 最优子结构性质。1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，每作一次贪心选择就将所求问题简化为规模更小的子问题

7、。2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。0-1背包问题与背包问题0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题: 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。这2类问题都具

8、有最优子结构性质，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 贪心方法的数据选择策略1、以、以价值价值为量度标准为量度标准按价值从高到低的次序将物品一件件放到背包按价值从高到低的次序将物品一件件放到背包中中。2、以以容量容量作为量度作为量度按物品重量的从清到重次序来把物品放入背包。按物品重量的从清到重次序来把物品放入背包。3、采用、采用单位价值单位价值为度量标准为度量标准使物品的装入次序使物品的装入次序按按pi/wi比值的从大到小比值的从大到小来考来考虑。虑。用贪心策略求解背包问题时，首先要选出最用贪心策略求解背包问题时，首先要选出最优的度量标准。优的度量标准。算法思

9、路算法思路1).将各物体按将各物体按单位价值单位价值由高到低排序由高到低排序. 2).取价值最高者放入背包取价值最高者放入背包.3).计算背包剩余空间计算背包剩余空间.4).重复重复2-3直到背包剩余容量直到背包剩余容量=0或物体全部装或物体全部装入背包为止。入背包为止。用贪心算法解背包问题的基本步骤考虑下列情况的背包问题考虑下列情况的背包问题 n=3,M=20,(p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10) 其中的其中的4个可行解是：个可行解是：背包问题void Knapsack(int n,float M,float v,float w,float

10、 x) Sort(n,v,w); /计算每种物品单位重量的价值Vi/Wiint i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi; /允许放入一个物品的一部分void 0-1-Knapsack(int n,float M,float v,float w,float x) /不一定是最优解不一定是最优解 Sort(n,v,w); int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;0-1背包问题贪心选择

11、之所以不能得到最优解：因为无法保证最终能将背包装满，部分闲置的背包空间使总价值降低了。0-1背包问题与背包问题102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥2401002012030601010020601012030601010020802012020300-1背包背包物品价值及重量思考题-0/1背包问题在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有N种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为C，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物

12、品不得拿走多件。如何选择量度标准才能找到最优解？若N=2, w=100,10,10,p=20,15,15,C=105。利用价值贪心准则时所得结果是否是最优？问题: 设一个由N个城市v1,v2,vn组成的网络, ci,j 为从vi 到vj的代价不妨设ci,j = cj,i ,且ci,i= .一推销员要从某城市出发经过每城市一次且仅一次后返回出发地问如何选择路线使代价最小。抽象描述抽象描述:将城市以及之间的道路抽象为一个无向图G, G中每边的权值表示这段线路的代价. 问题转化为求一条最佳周游路线:从一点出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小. 1 2 7 51 4 4 32 4

13、 1 27 4 1 35 3 2 3 C=思考题-旅行商问题(Traveling Salesman Problem)费用矩阵思考题-旅行商问题(货郎担问题) 首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点： 1)不会有三条边(候选边及已入选边)与同一顶点相关联。 2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。最后求得的回路是125341，代价是14。实际图11最小代价的回路是12543一1，代价是10。输入:城市的数目n,代价矩阵c

14、=c(1.n,1.n).输出: 最小代价路线1. tour:=0; / tour 纪录路线/2. cost:=0; / cost 纪录到目前为止的花费/3. v:=N; / N为起点城市, v为当前出发城市/4. for k:=1 to N-1 do 5. tour:= tour+(v,w) /(v,w)为从v到其余城市代价中值最小的边/6. cost:= cost+c(v,w) 7 v:=w8 tour:= tour+(v,N)9 cost:= cost+c(v,N) print tour, cost 算法的最坏时间复杂性为O(n2)*该算法不能求的最优解.思考题-旅行商问题(货郎担问题)3

15、.3 最优装载有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题可形式化描述为其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。nixcxwxiniiinii110max11，3.3 最优装载例例设设N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。所考察货箱的次序为所考察货箱的次序为 t1.8=7, 3, 6, 8, 4, 1, 5, 2。货箱。货箱7, 3, 6, 8, 4, 1的总重量为的总重量为390个单位且已被装载个单位且已被装

16、载, 剩下的装载能力为剩下的装载能力为10 ,小于任意货箱小于任意货箱.所以得到解所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1算法思路算法思路 将装船过程划为多步选择，每步装一个将装船过程划为多步选择，每步装一个货箱，每次货箱，每次从剩下的货箱中选择重量最轻的货箱从剩下的货箱中选择重量最轻的货箱.如如此下去直到所有货箱均装上船或船上不能再容纳其此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。他任何一个货箱。3.3 最优装载算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。void Loading(int x

17、, Type w, Type c, int n) int *t = new int n+1;Sort(w, t, n); /按货箱重量排序按货箱重量排序O(nlogn)for (int i = 1; i = n; i+) xi = 0; /O(n)for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti; /调整剩余空间调整剩余空间思考设设N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。编程求t 哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。哈夫曼编码压缩率

18、通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。3.4 哈夫曼编码例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长编码需要300,000位，而按表中变长编码方案，文件的总码长为：（451+133+123+163+94+54）1000=224,000。比用定长码方案总码长较少约45%。1.前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法

19、非常简单。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。平均码长定义为：码长: )()()()(cdcdcfTBTTCc使平均码长达到最小的前缀码编码方案称为使平均码长达到最小的前缀码编码方案称为给定编码字符集给定编码字符集C的最优前缀码。的最优前缀码。2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。2.构造哈夫曼树构造最优二叉树的算法是由哈夫曼提出的，所以称之为哈夫曼算法，具体叙述如下： 根据

20、与n个权值w1,w2,.,wn对应的n个结点构成n棵二叉树的森林F=T1,T2,.,Tn,其中每棵二叉树Ti(1=i=n)都由一个权值为wi的根结点，其左右子树均为空； 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左右子树，且置新树的附加根结点的权值为其左右子树上根结点的权值之和； 从F中删除这两棵树，同时把新树加入F中； 重复(2)和(3)，直到F中只含有一棵树为止。此树便是哈夫曼树。算法说明在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并

21、后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。3.5 单源最短路径(Single-Source Shortest-Paths Problem) 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。单源最短路径

22、问题：已知图G（V，E），找出从某给定的源结点SV到V中的每个结点的最短路径。3.5.1 Dijkstra算法Dijkstra算法是解单源最短路径问题的贪心算法。基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。（1）初始时，S中仅含有源节点。（2）设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，用数组Di记录顶点i当前所对应的最短特殊路径长度。（3）Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组D作必要的修改。（4）一旦S包含了所有V中顶点，dist

23、就记录了从源到所有其它顶点之间的最短路径长度。1、 Dijkstra算法的基本思想设S为最短距离已确定的顶点集（红点集）V-S是最短距离尚未确定的顶点集（蓝点集）。初始化初始化 最初只有源点s的最短距离是已知的(D(s)=0)，故红点集S=s 。重复以下工作，重复以下工作，按路径长度递增次序产生各顶点最短路按路径长度递增次序产生各顶点最短路径径 在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。 当蓝点集中仅剩下最短距离为的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。一个实例Dijkstra(G，D，s) /Di

24、jkstra 算法算法 O(V2) /初始化操作初始化操作 S=s；Ds=0； /设置初始的红点集及最短距离设置初始的红点集及最短距离 for( all i V-S ) Di=Gsi； /O(V) /扩充红点集扩充红点集 for (i=1;iDk+Gkj) Dj=Dk+Gkj； #define VEX 5/定义结点的个数定义结点的个数#define maxpoint 100double graphmaxpoint= 0 , 10 , -1 , 30 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20 , 0

25、, 60 , -1 , -1 , -1 , -1 , 0 ; /邻接矩阵，邻接矩阵，-1代表节点间无边相连代表节点间无边相连int Rmaxpoint=0,Bmaxpoint;int DVEX,PVEX;/定义数组定义数组D用来存放结点特殊用来存放结点特殊距离，距离，P数组存放父亲结点数组存放父亲结点/初始时，红点集中仅有源结点初始时，红点集中仅有源结点0R0=1; B0=0;for(int i=1;iVEX;i+) /初始化蓝点集节点初始化蓝点集节点Bi=1;/对数组对数组D、P进行初始化进行初始化 for(i=0;iVEX;i+)Di=graph0i; if(Di!=-1) Pi=0; e

26、lse Pi=-1;for(int k=1;kVEX;k+) /每次从蓝点集中取出具有最短特殊路长每次从蓝点集中取出具有最短特殊路长度的结点度的结点min for(int min=0;Bmin=0;) min+; for(int j=min;jVEX;j+) /求蓝点集结点最小下标元素求蓝点集结点最小下标元素if(Dj!=-1&DjDmin&Bj=1) min=j; coutmin=min ; /将具有最短特殊路长度的结点将具有最短特殊路长度的结点min添加到红点集中添加到红点集中 Rmin=1; Bmin=0; /对数组对数组D作必要的修改作必要的修改 for(j=1;jDmin+graph

27、minj|Dj=-1) Dj=Dmin+graphminj; /每次迭代求最小值，最后每次迭代求最小值，最后一次即为到源点的最短路径一次即为到源点的最短路径 Pj=min; 3.5.2 Dijkstra算法Relax描述du:su的距离 pu:记录前一节点Relax松弛算法Init-single-source(G,s) for each vVG dodv= pv=NIL ds=0, ps=NILRelax(u,v,w) if dvdu+w(u,v)then dv=du+wu,v pv=u 算法描述dijkstra(G,w,s)1. Init-single-source(G,s) /O(v)2.

28、 S=s 3. Q=VG-s4.while Q do u=min(Q) /用数组O(V) S=Su for each vadju & v Q /O(E) do Relax(u,v,w)算法基本思想3.5.3 Bellman-Ford算法思想 dijkstra算法的前提是所有边是正的 Bellman-Ford算法允许负边 初始化：将除源点外的所有顶点的最短距离估计值 dv +, ds 0; 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）(1) 检验负权回路：如果存在负边，则算法返回false，表明问题无解；否则算法

29、返回true，并且从源点可达的顶点v的最短距离保存在 dv中。3.5.3 Bellman-Ford算法思想dijkstra算法的前提是所有边是正的Bellman-Ford算法允许负边 Init-single-source(G,s) for i 1 to |VG| - 1 /O(V) 3. do for each edge (u, v) EG/O(E)4. do RELAX(u, v, w) 5. for each edge (u, v) EG /O(E)6. do if du + w(u, v) dv 7. then return FALSE /存在负环8. return TRUE存在负权回路

30、的图是不能求两点间最短路径，因为存在负权回路的图是不能求两点间最短路径，因为只要在负权回路上不断兜圈子，所得的最短路长度只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。可以任意小。3.5.4 其他最短路径问题其他最短路径问题单目标单目标最短路径问题最短路径问题(Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。单顶点对单顶点对间最短路径问题间最短路径问题(Single-Pair Shortest-Paths Problem)：对

31、于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。所有顶点对所有顶点对间最短路径问题间最短路径问题(All-Pairs Shortest-Paths Problem)：对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。3.6 最小生成树设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生

32、成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。1、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。Prim算法和Kruskal算法2个算法都利用了最小生成树性质：最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(uU)里、另一个端点不在U(即vV-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边

33、(u，v)。这个性质称为MST（Minimum Spanning Tree ）性质。1、最小生成树性质MST性质的证明： 约定：集合U中的顶点红色顶点V-U中的顶点蓝色顶点连接红点和蓝点的边紫色边权最小的紫边称为轻边(即权重最“轻”的边)。用反证法证明MST性质1、最小生成树性质假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u ，v )连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(u ，v )后回路亦

34、消除，由此可得另一生成树T 。 T 和T的差别仅在于T用轻边(u，v)取代了T中权重可能更大的紫边(u ，v )。因为w(u，v)w(u ，v )，所以 w(T)=w(T)+w(u，v)-w(u，v)w(T)故T亦是G的MST，它包含边(u，v)，这与假设矛盾。 所以，MST性质成立。2、Prim（普里姆）算法设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置U=1，然后，只要U是V的真子集，就作如下的贪心选择：选取满足条件iU，jV-U，且cij最小的边，将顶点j添加到U中。这个过程一直进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的

35、一棵最小生成树。例如，对于右图中的带权图，按Prim算法选取边的过程如图所示。2、Prim（普里姆）算法PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T中 T=；U=1; while(U!=V) /O(V) (i,j)=iU，jV-U，且cij最小的边/O(V) T=T (i，j) /轻边 (i，j) 加入T U=U j; / 节点j 加入U，变为红点 http:/ 2、Prim（普里姆）算法如何有效地找出满足条件iU, jV-U，且权cij最小的边(i,j)？ 较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-U中使lowco

36、st值最小的顶点j，然后根据数组closest选取边(j,closestj)，将j添加到U中，并对closest和lowcost作必要的修改。3、Kruskal（克鲁斯卡尔）算法Kruskal算法构造最小生成树的基本思想：(1)将G的n个顶点看成n个孤立的连通分支。(2)将所有的边按权从小到大排序。(3)从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直

37、接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如图所示。3、Kruskal（克鲁斯卡尔）算法（1）算法思想T的初始状态 只有n个顶点而无边的森林T=(V， )按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST注意： 安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树 因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树 3、Kruskal（克鲁斯卡尔）算法MST-Kruskal (G) /求连通网G

38、的一棵MST T=(V，)； /初始化，T是只含n个顶点不包含边的森林/依权值递增序对E(G)中的边排序，并设结果在E0.e-1中 O(Elog(E)sort the edges of E by non-decreasing weight w for(i=0;ie;i+) /e为图中边总数，O(E) 取第i条边（u,v） if u和v分别属于T中两棵不同的树 T=T(u，v)；/(u，v)是安全边，将其加入T中 return T；说明有关说明： 该算法的时间复杂度为O(ElogE)。 Kruskal算法的时间主要取决于边数。它较适合于稀疏图。 3.7 多机调度问题设有 n 个独立的作业 1 ,

39、 2 , . , n ，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为 ti。约定： 任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。 任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成。3.7 多机调度问题这个问题是NP完全问题(Non-deterministic Polynomial Complete Problem) ，也即是多项式复杂程度的非确定性问题 ，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。非确定性问题:无法按部就班直接地计算出来。比如，找大质数的问题。没