2010-5-14 计算机算法设计与分析 1
第三章
贪心算法
2010-5-14 计算机算法设计与分析 2
贪心算法的特点
? 贪心算法总是作出在当前来看是最好的选择。
? 就是说，贪心算法并不从整体最优上来考虑，
所作出的选择只是某种意义上的局部最优选择。
? 当然希望贪心算法得到的最终结果是最优的。
? 可是贪心算法并不能保证最终结果是最优的。
? 不过，在许多的情况下，应用贪心算法能够得
到整体最优解；并且在一些情况下，即使得到
的不是最优解，也是一个很好的近似解。
2010-5-14 计算机算法设计与分析 3
贪心算法的一般框架
? GreedyAlgorithm(parameters){
? 初始化；
? 重复执行以下的操作：
? 选择当前可以选择的 (相容 )最优解；
? 将所选择的当前解加入到问题的解中；
? 直至满足问题求解的结束条件。
? }
2010-5-14 计算机算法设计与分析 4
最小生成树
? 设 G = (V,E)是一个无向连通带权图，即一个网
络。 E的每条边 (v,w)的权为 c[v][w]。
? 如果 G的一个子图 G’是一棵包含 G的所有顶点
的树，则称 G’为 G的生成树。
? 生成树的各边的权的总和称为该生成树的耗费。
? 在 G的所有生成树中，耗费最小的生成树称为
G的最小 (优 )生成树。
2010-5-14 计算机算法设计与分析 5
树的基本性质
? 连通无回路的图 G称为树。
? 树是点比边多一的连通图,G连通且 q=p–1 。
? 树是点比边多一的无回路图,G无回路且 q=p–1。
? 树若添条边就有回路,G无回路，但对任意的 u,
v∈ V(G),若 uv?E(G),则 G+uv中恰有一条回路。
? 树若减条边就不连通,G连通，但对 ?e∈ E(G),
G–e不连通。
? n个顶点的连通图的生成树含有 n – 1条边。
2010-5-14 计算机算法设计与分析 6
最小生成树的贪心选择性质
? 令 G中权最小的边为 e1。首先必定有图 G的一棵
最小生成树包含了 e1。
若 G的任何最小生成树都不包含 e1。设 T为 G的
最小生成树,e1?T。于是 T+e1是一个有回路的
图且该回路中包含 e1。该回路中必有条不是 e的
边 ei。令 T’={T+e1}–ei。 T’也是 G的生成树。又
c(T’) = c(T) + c(e1) – c(e1),c(e1) ≤ c(ei)，从而
c(T’)≤c(T),T’是 G的最小生成树且含有边 e1。
矛盾。故必定有图 G的最小生成树包含了 e1。
? 选定第一条边 e1以后，该如何选择第二条边呢？
? 依据各条边的权重，依次选出权重较轻的 n – 1
条边。这 n – 1条边必定包括了 G的 n个顶点。这
样就得到了 G的一棵最小生成树。
这样做是否可以呢？? 不行！因为不能保证这 n – 1条边构成树？要保证这 n – 1条边构成树，必须使这 n – 1条边
是连通的或者是无回路的。
Prim算法的做法：在保证连通的前提下依次选
出权重较小的 n – 1条边（在实现中体现为 n个
顶点的选择）。
Kruskal算法的做法：在保证无回路的前提下依
次选择权重较小的 n – 1条边。
2010-5-14 计算机算法设计与分析 7
Prim算法
? 基本思想：在保证连通的前提下依次选出权重
较小的 n – 1条边。
? G=(V,E)为无向连通带权图，令 V={1,2,…,n} 。
? 设置一个集合 S,初始化 S = {1},T = Φ。
? 贪心策略：如果 V–S中的顶点 j与 S中的某个点 i
连接且 (i,j)是 E中的权重最小的边，于是就选择
j(将 j加入 S)，并将 (i,j) 加入 T中 。
? 重复执行贪心策略，直至 V–S为空。
2010-5-14 计算机算法设计与分析 8
Prim算法中的数据结构
? 图用连接矩阵 C[i][j]给出，即 C[i][j]为结点 i到
结点 j的权重。
? 为了有效地找出 V–S中满足与 S中的某个点 i连
接且 (i,j) 权重最小的顶点 j，对其中的每个顶点
j设立两个数组 closest[j]和 lowcost[j]：
? closest[j]是 s中与 j最近的顶点,(closest[j],j)即
为选中的边，而 lowcost[j]是相应边的权重。
2010-5-14 计算机算法设计与分析 9
Prim算法的实现
? Prim(int n,Type **c) {
初始化：结点 1放入 S；并初始化 lowcost[]和
closest[]；
执行以下操作 n–1次：
依据 lowcost[]找出与 S最近的点 j并放入 S；
调整 lowcost[]和 closest[]； }
int j = 1; s[j] = true;
for (int i = 2; i <= n; i++) {
closest[i] = 1; lowcost[i]=c[1][i]; s[i]=false;}
for (int i = 1; i < n; i++) {min= inf;
for (int k = 2; k <= n; k++) {
if (lowcost[k]<min&&!s[k])
{min = lowcost[k]; j = k}
s[j] = true;
s中仅加入了一个新成员 j，因此只需要
依据结点 j调整 lowcost[]和 closest[]；
for (int k = 2; k <= n; k++) {
if (c[j][k]< lowcost[k]&&!s[k])
{lowcost[k] = c[j][k]; closest[k] = j}}}
2010-5-14 计算机算法设计与分析 10
Prim算法的示例
? 给定一个连通带权图如下：
1
2
3
4
5 6
16 55
5
3 6
6
24
? 初始时 S={1},T= Φ；
? 第一次选择：
∵ (1,3)权最小
∴ S={1,3}
T= {(1,3)} ；
第二次选择：
∵ 3 6 权最小
∴,6}，
,(3,6)} ；
第三次选择：
∵ 6 4 权最小
∴,4}，
,(6,4)} ；
第四次选择：
∵ 2 权最小
∴,2}，
,
(2,3)} ；
第五次选择：
∵ 5 2 权最小
∴,5}，
(3,2) (2,5)} ；
2010-5-14 计算机算法设计与分析 11
Kruskal算法
? 基本思想：在保证无回路的前提下依次选出权
重较小的 n – 1条边。
? 贪心策略：如果 (i,j)是 E中尚未被选中的边中权
重最小的，并且 (i,j)不会与已经选择的边构成
回路，于是就选择 (i,j)。
问题：如何知道 (i,j)不会造成回路？? 若边 (i,j) 的两个端点 i和 j属于同一个连通分支，
则选择 (i,j) 会造成回路，反之则不会造成回路。
? 因此初始时将图的 n个顶点看成 n个孤立分支。
2010-5-14 计算机算法设计与分析 12
Kruskal算法的数据结构
? 数组 e[][]表示图的边,e[i][u],e[i][v]和 e[k][w]
分别表示边 i的两个端点及其权重。
? 函数 Sort(e,w)将数组 e按权重 w从小到大排序。
? 一个连通分支中的顶点表示为一个集合。
? 函数 Initialize(n)将每个顶点初始化为一个集合。
? 函数 Find(u)给出顶点 u所在的集合。
? 函数 Union(a,b)给出集合 a和集合 b的并集。
? 重载算符 !=判断集合的不相等。
2010-5-14 计算机算法设计与分析 13
Kruskal算法的实现
Kruskal(int n,**e) {
Sort(e,w); //将边按权重从小到大排序
initialize(n); //初始时每个顶点为一个集合
k = 1; //k累计已选边的数目，
j = 1; //j为所选的边在 e中的序号
while (k < n) //选择 n – 1条边
{a = Find(e[j][u]); b = Find(e[j][v]);
//找出第 j条边两个端点所在的集合
if (a != b) {t[k++] = j; Union(a,b)}
//若不同，第 j条边放入树中并合并这两个集合
j++ }} //继续考察下一条边
2010-5-14 计算机算法设计与分析 14
Kruskal算法的例子
1
2
3
4
5 6
16 55
5
3 6
6
24
1 3 1
4 6 2
2 5 3
3 6 4
1 4 5
2 3 5
3 4 5
1 2 6
3 5 6
5 6 6
初始时为 6个孤立点
1
2
3
4
5 6
选择了边 1，于是 1,3点合
并为同一个集合。 √
选择了边 2，于是 4,6点合
并为同一个集合。 √
选择了边 3，于是 2,5点合
并为同一个集合。
√
选择了边 4，于是 1,3,4、
6点合并为同一个集合。
√
考察边 5，因为 1,4点属于
同一个集合，被放弃。
×
选择边 6，于是 1,3,4,6、
2,5点属于同一个集合。
√
已经选择边了 n–1条边，算
法结束。结果如图所示。
u v w
2010-5-14 计算机算法设计与分析 15
Prim与 Kruskal两算法的复杂性
? Prim算法为两重循环，外层循环为 n次，内层
循环为 O(n)，因此其复杂性为 O(n2)。
? Kruskal算法中，设边数为 e，则边排序的时间
为 O(e)，确定边的时间为 O(loge)，所以整个时
间复杂性为 O(eloge)。
? 当 e = Ω(n2)时,Kruskal算法要比 Prim算法差；
? 当 e = ο(n2)时,Kruskal算法比 Prim算法好得多。
2010-5-14 计算机算法设计与分析 16
贪心算法也能获得最优解
? 用 Kruskal算法得到的 生成树 T*必是最优树。
? 证明,设 T*不是最优，令 T是与 T*有 k条共同边
的最优树且 k是最优树与 T*共有边数的 最大值 。
? ∵ T≠T* ∴ ?ek+1,ek+1? E(T)且 ek+1∈ E(T*)。
? 则 T+ek+1含唯一回路 C,C必有条边 ek’?E(T*)。
? 令 T’= (T+ek)– ek’,w(T’)=w(T)+w(ek+1) –w(ek’)。
? 由算法知,w(ek+1) ? w(ek’),∴ T’是最优树。
? 但 T’与 T*有 k+1条共同边，矛盾。故 T*是最优。
2010-5-14 计算机算法设计与分析 17
0-1背包问题
? 给定 n个物品和一个背包。物品 i的重量为 wi，
价值为 vi，背包容量为 c。问如何选择装入背包
中的物品，使得装入背包的物品的价值最大？
? 在装入背包时，每种物品 i只有两种选择，装入
或者不装入，既不能装入多次，也不能只装入
一部分。因此，此问题称为 0-1背包问题。
? 如果在装入背包时，物品可以切割，即可以只
装入一部分，这种情况下的问题称为背包问题。
2010-5-14 计算机算法设计与分析 18
0-1背包问题不适用贪心算法
? 背包容量为 50kg，物品 1,2和 3的容量和价值分
别为 (10kg,$60),(20kg,$100)和 (30kg,$120)。
? 单位重量价值最高的为物品 1,6$/kg。但是依
照贪心算法首选物品 1却不能获得最优解：
物品 1
物品 2
物品 1
物品 3
物品 2
物品 3
总价
值为
$160,
空余
20 kg
总价
值为
$180,
空余
10 kg
总价
值为
$220,
没有
空余 。
? 但是背包问题却是适用贪心算法的。
2010-5-14 计算机算法设计与分析 19
贪心算法的基本要素
? 贪心算法的基本要素是,贪心选择性质 。
? 所谓贪心选择性质是指所求问题的整体最优解
可以通过一系列局部最优解的选择，即贪心选
择来达到。
? 贪心选择每次选取当前最优解，因此它依赖以
往的选择，而不依赖于将来的选择。
? 贪心算法通常以自顶向下的方式进行，每次贪
心选择就将原问题转化为规模更小的子问题。
2010-5-14 计算机算法设计与分析 20
如何确定贪心选择性质
? 证明贪心选择将导致整体的最优解：
? 首先证明存在问题的一个整体最优解必
定包含了第一个贪心选择。
? 然后证明在做了贪心选择后，原问题简
化为规模较小的类似子问题，即可继续
使用贪心选择。
? 于是用数学归纳法可证明，经过一系列
贪心选择可以得到整体最优解。
2010-5-14 计算机算法设计与分析 21
单源最短路径
? 给定一个图 G = (V,E)，其中每条边的权
是一个非负实数。另外给定 V中的一个顶
点 v，称为源。求从源 v到所有其它各个
顶点的最短路径。
? 单源最短路径问题的贪心选择策略：选
择从源 v出发目前用最短的路径所到达的
顶点，这就是目前的局部最优解。
2010-5-14 计算机算法设计与分析 22
单源最短路径的贪心算法
? 基本思想：首先设置一个集合 S；用数组 dis[]来
记录 v到 S中各点的目前最短路径长度。然后不
断地用贪心选择来扩充这个集合，并同时记录或
修订数组 dis[]；直至 S包含所有 V中顶点。
? 贪心选择：一个顶点 u属于 S当且仅当从 v到 u的
最短路径长度已知。
? 初始化,S中仅含有源 v。
2010-5-14 计算机算法设计与分析 23
Dijkstra 算法
? Dijkstra 算法的做法是：
? 由近到远逐步计算，每次最近的顶点的
距离就是它的最短路径长度。
? 然后再从这个最近者出发。即依据最近
者修订到各顶点的距离，然后再选出新
的最近者。
? 如此走下去，直到所有顶点都走到。
2010-5-14 计算机算法设计与分析 24
Dijkstra 算法
Procedure Dijkstra {
(1) S:={1}; //初始化 S
(2) for i:= 2 to n do //初始化 D
(3) dis[i] =C[1,i] ; //初始时为源到顶点 i一步的距
离
(4) for i,=1 to n-1 do {
(5) 从 V-S中选取一个顶点 u使得 dis[u]最小；
(6) 将 u加入到 S中； //将新的最近者加入 S
(7) for ?w∈ V-S do //依据最近者 u修订 dis[v]
(8) dis[w],= min(dis[w],dis[u]+C[u,w)
}
}
2010-5-14 计算机算法设计与分析 25
Dijkstra算法举例
迭代 S u dis[2] dis[3] dis[4] dis[5]
初始 {1} -- 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5} 5 10 50 30 60
1
2 5
43
10
20
50
100
30
10 60
赋权图 G
由数组 D[i]可知：从顶点 1到顶点 2,3,4,5的
最短通路的长度分别为 10,50,30和 60。
2010-5-14 计算机算法设计与分析 26
Dijkstra算法的贪心选择性质
? Dijkstra 算法中所做的贪心选择是：若 u是 V–S
中具有最短路径的特殊顶点，就将 u选入 S，并
确定了从源到 u的最短路径长度 D[u]。
? 为什么从源到 u没有更短的路径呢？
? 若有，则将如下图所示：
S
v
dis[u]
(最近距离 ) u
xdis[x]
若该路径经 S外一点
x到达 u，则：
dis[x]+d(x,u)＜ dis[u]
从而 dis[x]＜ dis[u]，
这与 u的选取矛盾
2010-5-14 计算机算法设计与分析 27
Dijkstra算法的计算复杂性
? Dijkstra 算法有两层循环，外层循环为 n次，内
层有两个循环：一个是选出最小的 w(第 5行 )，
另一个是修订 D[v](第 7,8行 )。它们的次数都
是 n/2，所以内层循环的时间为 O(n)。
? 因此 Dijkstra算法的时间复杂度为 O(n2)
? Dijkstra 算法能求出从源到其它各顶点的最短
通路的长度，但是却并没有给出其最短通路。
? 对 Dijkstra 算法做适当的修改便可求出最短通
路。同学们可以自己去修改算法并编程实现。
2010-5-14 计算机算法设计与分析 28
贪心算法小结
? 贪心算法每次选择目前最优的解，即通过一系
列局部最优来获得整体最优。
? 贪心算法只有在具有贪心选择性质时才能保证
获得整体最优。
? 证明贪心选择性质：⑴第一个选择是对的；⑵
在作出贪心选择后原问题转化为同样的子问题；
⑶由归纳法知问题具有贪心选择性质。
? 若原问题是求带权拟阵的最优独立子集问题，
则必满足贪心选择性质。
第三章
贪心算法
2010-5-14 计算机算法设计与分析 2
贪心算法的特点
? 贪心算法总是作出在当前来看是最好的选择。
? 就是说，贪心算法并不从整体最优上来考虑，
所作出的选择只是某种意义上的局部最优选择。
? 当然希望贪心算法得到的最终结果是最优的。
? 可是贪心算法并不能保证最终结果是最优的。
? 不过，在许多的情况下，应用贪心算法能够得
到整体最优解；并且在一些情况下，即使得到
的不是最优解，也是一个很好的近似解。
2010-5-14 计算机算法设计与分析 3
贪心算法的一般框架
? GreedyAlgorithm(parameters){
? 初始化；
? 重复执行以下的操作：
? 选择当前可以选择的 (相容 )最优解；
? 将所选择的当前解加入到问题的解中；
? 直至满足问题求解的结束条件。
? }
2010-5-14 计算机算法设计与分析 4
最小生成树
? 设 G = (V,E)是一个无向连通带权图，即一个网
络。 E的每条边 (v,w)的权为 c[v][w]。
? 如果 G的一个子图 G’是一棵包含 G的所有顶点
的树，则称 G’为 G的生成树。
? 生成树的各边的权的总和称为该生成树的耗费。
? 在 G的所有生成树中，耗费最小的生成树称为
G的最小 (优 )生成树。
2010-5-14 计算机算法设计与分析 5
树的基本性质
? 连通无回路的图 G称为树。
? 树是点比边多一的连通图,G连通且 q=p–1 。
? 树是点比边多一的无回路图,G无回路且 q=p–1。
? 树若添条边就有回路,G无回路，但对任意的 u,
v∈ V(G),若 uv?E(G),则 G+uv中恰有一条回路。
? 树若减条边就不连通,G连通，但对 ?e∈ E(G),
G–e不连通。
? n个顶点的连通图的生成树含有 n – 1条边。
2010-5-14 计算机算法设计与分析 6
最小生成树的贪心选择性质
? 令 G中权最小的边为 e1。首先必定有图 G的一棵
最小生成树包含了 e1。
若 G的任何最小生成树都不包含 e1。设 T为 G的
最小生成树,e1?T。于是 T+e1是一个有回路的
图且该回路中包含 e1。该回路中必有条不是 e的
边 ei。令 T’={T+e1}–ei。 T’也是 G的生成树。又
c(T’) = c(T) + c(e1) – c(e1),c(e1) ≤ c(ei)，从而
c(T’)≤c(T),T’是 G的最小生成树且含有边 e1。
矛盾。故必定有图 G的最小生成树包含了 e1。
? 选定第一条边 e1以后，该如何选择第二条边呢？
? 依据各条边的权重，依次选出权重较轻的 n – 1
条边。这 n – 1条边必定包括了 G的 n个顶点。这
样就得到了 G的一棵最小生成树。
这样做是否可以呢？? 不行！因为不能保证这 n – 1条边构成树？要保证这 n – 1条边构成树，必须使这 n – 1条边
是连通的或者是无回路的。
Prim算法的做法：在保证连通的前提下依次选
出权重较小的 n – 1条边（在实现中体现为 n个
顶点的选择）。
Kruskal算法的做法：在保证无回路的前提下依
次选择权重较小的 n – 1条边。
2010-5-14 计算机算法设计与分析 7
Prim算法
? 基本思想：在保证连通的前提下依次选出权重
较小的 n – 1条边。
? G=(V,E)为无向连通带权图，令 V={1,2,…,n} 。
? 设置一个集合 S,初始化 S = {1},T = Φ。
? 贪心策略：如果 V–S中的顶点 j与 S中的某个点 i
连接且 (i,j)是 E中的权重最小的边，于是就选择
j(将 j加入 S)，并将 (i,j) 加入 T中 。
? 重复执行贪心策略，直至 V–S为空。
2010-5-14 计算机算法设计与分析 8
Prim算法中的数据结构
? 图用连接矩阵 C[i][j]给出，即 C[i][j]为结点 i到
结点 j的权重。
? 为了有效地找出 V–S中满足与 S中的某个点 i连
接且 (i,j) 权重最小的顶点 j，对其中的每个顶点
j设立两个数组 closest[j]和 lowcost[j]：
? closest[j]是 s中与 j最近的顶点,(closest[j],j)即
为选中的边，而 lowcost[j]是相应边的权重。
2010-5-14 计算机算法设计与分析 9
Prim算法的实现
? Prim(int n,Type **c) {
初始化：结点 1放入 S；并初始化 lowcost[]和
closest[]；
执行以下操作 n–1次：
依据 lowcost[]找出与 S最近的点 j并放入 S；
调整 lowcost[]和 closest[]； }
int j = 1; s[j] = true;
for (int i = 2; i <= n; i++) {
closest[i] = 1; lowcost[i]=c[1][i]; s[i]=false;}
for (int i = 1; i < n; i++) {min= inf;
for (int k = 2; k <= n; k++) {
if (lowcost[k]<min&&!s[k])
{min = lowcost[k]; j = k}
s[j] = true;
s中仅加入了一个新成员 j，因此只需要
依据结点 j调整 lowcost[]和 closest[]；
for (int k = 2; k <= n; k++) {
if (c[j][k]< lowcost[k]&&!s[k])
{lowcost[k] = c[j][k]; closest[k] = j}}}
2010-5-14 计算机算法设计与分析 10
Prim算法的示例
? 给定一个连通带权图如下：
1
2
3
4
5 6
16 55
5
3 6
6
24
? 初始时 S={1},T= Φ；
? 第一次选择：
∵ (1,3)权最小
∴ S={1,3}
T= {(1,3)} ；
第二次选择：
∵ 3 6 权最小
∴,6}，
,(3,6)} ；
第三次选择：
∵ 6 4 权最小
∴,4}，
,(6,4)} ；
第四次选择：
∵ 2 权最小
∴,2}，
,
(2,3)} ；
第五次选择：
∵ 5 2 权最小
∴,5}，
(3,2) (2,5)} ；
2010-5-14 计算机算法设计与分析 11
Kruskal算法
? 基本思想：在保证无回路的前提下依次选出权
重较小的 n – 1条边。
? 贪心策略：如果 (i,j)是 E中尚未被选中的边中权
重最小的，并且 (i,j)不会与已经选择的边构成
回路，于是就选择 (i,j)。
问题：如何知道 (i,j)不会造成回路？? 若边 (i,j) 的两个端点 i和 j属于同一个连通分支，
则选择 (i,j) 会造成回路，反之则不会造成回路。
? 因此初始时将图的 n个顶点看成 n个孤立分支。
2010-5-14 计算机算法设计与分析 12
Kruskal算法的数据结构
? 数组 e[][]表示图的边,e[i][u],e[i][v]和 e[k][w]
分别表示边 i的两个端点及其权重。
? 函数 Sort(e,w)将数组 e按权重 w从小到大排序。
? 一个连通分支中的顶点表示为一个集合。
? 函数 Initialize(n)将每个顶点初始化为一个集合。
? 函数 Find(u)给出顶点 u所在的集合。
? 函数 Union(a,b)给出集合 a和集合 b的并集。
? 重载算符 !=判断集合的不相等。
2010-5-14 计算机算法设计与分析 13
Kruskal算法的实现
Kruskal(int n,**e) {
Sort(e,w); //将边按权重从小到大排序
initialize(n); //初始时每个顶点为一个集合
k = 1; //k累计已选边的数目，
j = 1; //j为所选的边在 e中的序号
while (k < n) //选择 n – 1条边
{a = Find(e[j][u]); b = Find(e[j][v]);
//找出第 j条边两个端点所在的集合
if (a != b) {t[k++] = j; Union(a,b)}
//若不同，第 j条边放入树中并合并这两个集合
j++ }} //继续考察下一条边
2010-5-14 计算机算法设计与分析 14
Kruskal算法的例子
1
2
3
4
5 6
16 55
5
3 6
6
24
1 3 1
4 6 2
2 5 3
3 6 4
1 4 5
2 3 5
3 4 5
1 2 6
3 5 6
5 6 6
初始时为 6个孤立点
1
2
3
4
5 6
选择了边 1，于是 1,3点合
并为同一个集合。 √
选择了边 2，于是 4,6点合
并为同一个集合。 √
选择了边 3，于是 2,5点合
并为同一个集合。
√
选择了边 4，于是 1,3,4、
6点合并为同一个集合。
√
考察边 5，因为 1,4点属于
同一个集合，被放弃。
×
选择边 6，于是 1,3,4,6、
2,5点属于同一个集合。
√
已经选择边了 n–1条边，算
法结束。结果如图所示。
u v w
2010-5-14 计算机算法设计与分析 15
Prim与 Kruskal两算法的复杂性
? Prim算法为两重循环，外层循环为 n次，内层
循环为 O(n)，因此其复杂性为 O(n2)。
? Kruskal算法中，设边数为 e，则边排序的时间
为 O(e)，确定边的时间为 O(loge)，所以整个时
间复杂性为 O(eloge)。
? 当 e = Ω(n2)时,Kruskal算法要比 Prim算法差；
? 当 e = ο(n2)时,Kruskal算法比 Prim算法好得多。
2010-5-14 计算机算法设计与分析 16
贪心算法也能获得最优解
? 用 Kruskal算法得到的 生成树 T*必是最优树。
? 证明,设 T*不是最优，令 T是与 T*有 k条共同边
的最优树且 k是最优树与 T*共有边数的 最大值 。
? ∵ T≠T* ∴ ?ek+1,ek+1? E(T)且 ek+1∈ E(T*)。
? 则 T+ek+1含唯一回路 C,C必有条边 ek’?E(T*)。
? 令 T’= (T+ek)– ek’,w(T’)=w(T)+w(ek+1) –w(ek’)。
? 由算法知,w(ek+1) ? w(ek’),∴ T’是最优树。
? 但 T’与 T*有 k+1条共同边，矛盾。故 T*是最优。
2010-5-14 计算机算法设计与分析 17
0-1背包问题
? 给定 n个物品和一个背包。物品 i的重量为 wi，
价值为 vi，背包容量为 c。问如何选择装入背包
中的物品，使得装入背包的物品的价值最大？
? 在装入背包时，每种物品 i只有两种选择，装入
或者不装入，既不能装入多次，也不能只装入
一部分。因此，此问题称为 0-1背包问题。
? 如果在装入背包时，物品可以切割，即可以只
装入一部分，这种情况下的问题称为背包问题。
2010-5-14 计算机算法设计与分析 18
0-1背包问题不适用贪心算法
? 背包容量为 50kg，物品 1,2和 3的容量和价值分
别为 (10kg,$60),(20kg,$100)和 (30kg,$120)。
? 单位重量价值最高的为物品 1,6$/kg。但是依
照贪心算法首选物品 1却不能获得最优解：
物品 1
物品 2
物品 1
物品 3
物品 2
物品 3
总价
值为
$160,
空余
20 kg
总价
值为
$180,
空余
10 kg
总价
值为
$220,
没有
空余 。
? 但是背包问题却是适用贪心算法的。
2010-5-14 计算机算法设计与分析 19
贪心算法的基本要素
? 贪心算法的基本要素是,贪心选择性质 。
? 所谓贪心选择性质是指所求问题的整体最优解
可以通过一系列局部最优解的选择，即贪心选
择来达到。
? 贪心选择每次选取当前最优解，因此它依赖以
往的选择，而不依赖于将来的选择。
? 贪心算法通常以自顶向下的方式进行，每次贪
心选择就将原问题转化为规模更小的子问题。
2010-5-14 计算机算法设计与分析 20
如何确定贪心选择性质
? 证明贪心选择将导致整体的最优解：
? 首先证明存在问题的一个整体最优解必
定包含了第一个贪心选择。
? 然后证明在做了贪心选择后，原问题简
化为规模较小的类似子问题，即可继续
使用贪心选择。
? 于是用数学归纳法可证明，经过一系列
贪心选择可以得到整体最优解。
2010-5-14 计算机算法设计与分析 21
单源最短路径
? 给定一个图 G = (V,E)，其中每条边的权
是一个非负实数。另外给定 V中的一个顶
点 v，称为源。求从源 v到所有其它各个
顶点的最短路径。
? 单源最短路径问题的贪心选择策略：选
择从源 v出发目前用最短的路径所到达的
顶点，这就是目前的局部最优解。
2010-5-14 计算机算法设计与分析 22
单源最短路径的贪心算法
? 基本思想：首先设置一个集合 S；用数组 dis[]来
记录 v到 S中各点的目前最短路径长度。然后不
断地用贪心选择来扩充这个集合，并同时记录或
修订数组 dis[]；直至 S包含所有 V中顶点。
? 贪心选择：一个顶点 u属于 S当且仅当从 v到 u的
最短路径长度已知。
? 初始化,S中仅含有源 v。
2010-5-14 计算机算法设计与分析 23
Dijkstra 算法
? Dijkstra 算法的做法是：
? 由近到远逐步计算，每次最近的顶点的
距离就是它的最短路径长度。
? 然后再从这个最近者出发。即依据最近
者修订到各顶点的距离，然后再选出新
的最近者。
? 如此走下去，直到所有顶点都走到。
2010-5-14 计算机算法设计与分析 24
Dijkstra 算法
Procedure Dijkstra {
(1) S:={1}; //初始化 S
(2) for i:= 2 to n do //初始化 D
(3) dis[i] =C[1,i] ; //初始时为源到顶点 i一步的距
离
(4) for i,=1 to n-1 do {
(5) 从 V-S中选取一个顶点 u使得 dis[u]最小；
(6) 将 u加入到 S中； //将新的最近者加入 S
(7) for ?w∈ V-S do //依据最近者 u修订 dis[v]
(8) dis[w],= min(dis[w],dis[u]+C[u,w)
}
}
2010-5-14 计算机算法设计与分析 25
Dijkstra算法举例
迭代 S u dis[2] dis[3] dis[4] dis[5]
初始 {1} -- 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5} 5 10 50 30 60
1
2 5
43
10
20
50
100
30
10 60
赋权图 G
由数组 D[i]可知：从顶点 1到顶点 2,3,4,5的
最短通路的长度分别为 10,50,30和 60。
2010-5-14 计算机算法设计与分析 26
Dijkstra算法的贪心选择性质
? Dijkstra 算法中所做的贪心选择是：若 u是 V–S
中具有最短路径的特殊顶点，就将 u选入 S，并
确定了从源到 u的最短路径长度 D[u]。
? 为什么从源到 u没有更短的路径呢？
? 若有，则将如下图所示：
S
v
dis[u]
(最近距离 ) u
xdis[x]
若该路径经 S外一点
x到达 u，则：
dis[x]+d(x,u)＜ dis[u]
从而 dis[x]＜ dis[u]，
这与 u的选取矛盾
2010-5-14 计算机算法设计与分析 27
Dijkstra算法的计算复杂性
? Dijkstra 算法有两层循环，外层循环为 n次，内
层有两个循环：一个是选出最小的 w(第 5行 )，
另一个是修订 D[v](第 7,8行 )。它们的次数都
是 n/2，所以内层循环的时间为 O(n)。
? 因此 Dijkstra算法的时间复杂度为 O(n2)
? Dijkstra 算法能求出从源到其它各顶点的最短
通路的长度，但是却并没有给出其最短通路。
? 对 Dijkstra 算法做适当的修改便可求出最短通
路。同学们可以自己去修改算法并编程实现。
2010-5-14 计算机算法设计与分析 28
贪心算法小结
? 贪心算法每次选择目前最优的解，即通过一系
列局部最优来获得整体最优。
? 贪心算法只有在具有贪心选择性质时才能保证
获得整体最优。
? 证明贪心选择性质：⑴第一个选择是对的；⑵
在作出贪心选择后原问题转化为同样的子问题；
⑶由归纳法知问题具有贪心选择性质。
? 若原问题是求带权拟阵的最优独立子集问题，
则必满足贪心选择性质。
