《算法設(shè)計與分析基礎(chǔ)》（Python語言描述） 課件 第7章貪心法1

第7章每一步局部最優(yōu)—貪心法7.1貪心法概述7.2求解組合問題7.3求解圖問題7.4求解調(diào)度問題7.5哈夫曼編碼CONTENTS提綱1/867.1.1什么是貪心法7.1貪心法概述每一步總是做出在當(dāng)前看來是最好的選擇，也就是說貪心法不從整體最優(yōu)上考慮，所做出的僅是在某種意義上的局部最優(yōu)解。解向量x=（x0，x1，…，xn-1）sn-1s0s1s2x0x1起始狀態(tài)…x2snxn-1目標(biāo)狀態(tài)2/86每一步的局部最優(yōu)選擇僅依賴以前的決策，且不依賴于以后的決策。所有局部最優(yōu)解合起來不一定構(gòu)成整體最優(yōu)解。所以貪心法不能保證對所有問題都得到整體最優(yōu)解。因此采用貪心法求最優(yōu)解時，必須證明該算法的每一步上做出的選擇都必然得到整體最優(yōu)解。3/867.1.2貪心法求解問題具有的性質(zhì)1.最優(yōu)子結(jié)構(gòu)性質(zhì)如果一個問題的最優(yōu)解包含其子問題的最優(yōu)解，則稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。證明方法：采用反證法，先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后證明在這個假設(shè)下可以構(gòu)造出比原問題的最優(yōu)解更好的解，從而導(dǎo)致矛盾。4/862.貪心選擇性質(zhì)指整體最優(yōu)解可以通過一系列局部最優(yōu)選擇（即貪心選擇）來得到。證明方法：采用數(shù)學(xué)歸納法證明，即證明每一步所做的貪心選擇最終得到問題的整體最優(yōu)解。5/86問題描述：假設(shè)有n（1≤n≤30000）個孩子，現(xiàn)在給孩子們發(fā)一些小餅干，每個孩子最多只能給一塊餅干。每個孩子i有一個胃口值g[i]（1≤g[i]≤2^31-1），這是能滿足胃口的最小餅干尺寸，共有m塊餅干，每塊餅干j有一個尺寸s[j]。如果g[i]≤s[j]，那么將餅干j分發(fā)給孩子i時該孩子會得到滿足。

分發(fā)的目標(biāo)是盡可能滿足越多數(shù)量的孩子，設(shè)計一個算法求這個最大數(shù)值。

例如，g={1，2，3},s={1，1}，盡管有兩塊小餅干，由于尺寸都是1，只能讓胃口值是1的孩子滿足，所以結(jié)果是1。

要求設(shè)計如下方法： def

findContentChildren(self,

g,s)

->

int:7.1.3實(shí)戰(zhàn)—分發(fā)餅干（LeetCode455★）6/86解題目是求得到滿足的最多孩子數(shù)量，所以是一個求最優(yōu)解問題。很容易想到對于胃口為g[i]的孩子i，為其分發(fā)恰好滿足的最小尺寸的餅干j即min{j|g[i]≤s[j]}，不妨分發(fā)過程從最小胃口的孩子開始，為此將g遞增排序。對于每個s[i]，先在g查找剛好滿足g[i]≤s[j]的j，再將餅干j分發(fā)該孩子i。為了提高g中的查找性能，將s也遞增排序。7/86用ans表示得到滿足的最多孩子數(shù)量（初始為0）即最優(yōu)解，i從0開始遍歷g，j從0開始在s中查找：g[i]≤s[j]，說明為孩子i分發(fā)餅干j得到滿足，則將餅干j分發(fā)給孩子i，執(zhí)行ans++，同時執(zhí)行i++，j++繼續(xù)為下一個孩子分發(fā)合適的餅干。否則，孩子i得不到滿足，執(zhí)行j++繼續(xù)為其查找更大尺寸的餅干。最后的ans就是答案。8/86例如，g={3，1，5，3，8}，s={6，1，3，2}，排序后g={1，3，3，5，8}，s={1，2，3，6}，分發(fā)餅干的過程如下圖所示，結(jié)果ans=3。餅干s胃口g133581236ij找到最優(yōu)解9/861 class

Solution:2

def

findContentChildren(self,

g,s)

->

int:3

g.sort()

#默認(rèn)為遞增排序4

s.sort()5

ans=06

i,j=0,07

while

i<len(g)

and

j<len(s):8

if

g[i]<=s[j]:i,ans=i+1,ans+1 #i只有在滿足時增19

j+=1 #每次循環(huán)j增110

return

ans10/86如果將貪心選擇策略改為每個孩子i分發(fā)得到滿足的餅干j（不一定是最小尺寸的餅干），結(jié)果是否正確呢？11/867.1.4貪心法的一般求解過程①建立數(shù)學(xué)模型來描述問題。②把求解的問題分成若干個子問題。③對每一子問題求解，得到子問題的局部最優(yōu)解。④把子問題的解局部最優(yōu)解合成原問題的一個最優(yōu)解。12/861 defgreedy(a,n): #貪心算法框架2 x=[] #初始時，解向量為空3 foriinrange(0,n): #執(zhí)行n步操作4 xi=Select(a) #從輸入a中選擇一個當(dāng)前最好的分量5 ifFeasiable(xi): #判斷xi是否包含在當(dāng)前解中6 x=Union(xi) #將xi分量合并形成x7 returnx #返回生成的最優(yōu)解貪心法求解問題的算法框架13/86假設(shè)有n個活動S=（1，2，…，n），有一個資源，每個活動執(zhí)行時都要占用該資源，并且該資源任何時刻只能被一個活動所占用，一旦某個活動開始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。每個活動i有一個開始時間bi和結(jié)束時間ei（bi<ei），它是一個半開半閉時間區(qū)間[bi，ei），假設(shè)最早活動執(zhí)行時間為0。求一種最優(yōu)活動安排方案，使得安排的活動個數(shù)最多。7.2.1活動安排問題Ⅰ7.2求解組合問題14/86ejbj解biei(b)bi≥ejbj(a)bj≥eiejbiei對于兩個活動i和j，若滿足bj≥ei或bi≥ej，則它們是不重疊的，稱為兩個兼容活動。本問題就是在n個活動中選擇最多的兼容活動即求最多兼容活動的個數(shù)。15/86用數(shù)組A存放所有的活動，A[i].b（1≤i≤n）存放活動起始時間，A[i].e存放活動結(jié)束時間。貪心策略：每一步總是選擇執(zhí)行這樣的一個活動，它能夠使得余下的活動的時間最大化即余下活動中兼容活動盡可能多。為此先按活動結(jié)束時間遞增排序，再從頭開始依次選擇兼容活動（用B集合表示），從而得到最大兼容活動子集即包含兼容活動個數(shù)最多的子集。16/86i1234567891011開始時間b130535688212結(jié)束時間e4567891011121315求最大兼容活動集B的過程i=1：preend=0，活動1[1，4)的開始時間大于0，選擇它，preend=活動1的結(jié)束時間=4，B={1}。i=2：活動2[3，5)的開始時間小于preend，不選取。i=3：活動3[0，6)的開始時間小于preend，不選取。i=4：活動4[5，7)的開始時間大于preend，選擇它，preend=7，B={1，4}。i=5：活動5[3，8)的開始時間小于preend，不選取。17/86i1234567891011開始時間b130535688212結(jié)束時間e4567891011121315i=6：活動6[5，9)的開始時間小于preend，不選取。i=7：活動7[6，10)的開始時間小于preend，不選取。i=8：活動8[8，11)的開始時間大于preend，選擇它，preend=11，B={1，4，8}。i=9：活動9[8，12)的開始時間小于preend，不選取。i=10：活動10[2，13)的開始時間小于preend，不選取。i=11：活動11[12，14)的開始時間大于preend，選擇它，preend=14，B={1，4，8，11}。18/8601234567891011112131415234567891011i1234567891011開始時間b130535688212結(jié)束時間e456789101112131519/861 classAction: #活動類2 def__init__(self,b,e):3 self.b=b #活動起始時間4 self.e=e #活動結(jié)束時間5 def__lt__(self,other):

#用于按e遞增排序6 ifself.e<other.e:returnTrue7 else:returnFalse820/869 defgreedly(A): #貪心算法10 globalflag11 n=len(A)12 flag=[False]*n #初始化為False13 A.sort() #按e遞增排序14 preend=0; #前一個兼容活動的結(jié)束時間15 foriinrange(0,n):16 ifA[i].b>=preend:17 flag[i]=True #選擇A[i]活動18 preend=A[i].e1921/8620 defaction(A): #求解活動安排問題Ⅰ22 greedly(A)23 print("求解結(jié)果");24 print("選取的活動:",end='')25 cnt=026 foriinrange(0,len(A)):27 ifflag[i]:28 print("[%d,%d]"%(A[i].b,A[i].e),end='')29 cnt+=130 print("\n共%d個活動"%(cnt))22/86程序驗(yàn)證A=[Action(1,4),Action(3,5),Action(0,6),Action(5,7),\ Action(3,8),Action(5,9),Action(6,10),Action(8,11),\ Action(8,12),Action(2,13),Action(12,15)]action(A)23/86算法的主要時間花費(fèi)在排序上，排序時間為O(nlog2n)。所以整個算法的時間復(fù)雜度為O(nlog2n)。算法分析24/86算法證明所有活動按結(jié)束時間遞增排序，這里就是要證明若X是A的最優(yōu)解，X=X'∪{1}，則X'是A'={i∈A：ei≥b1}的最優(yōu)解。那么A是不是總存在一個以活動1開始的最優(yōu)解。如果第一個選擇的活動為k（k≠1），可以構(gòu)造另一個最優(yōu)解Y，Y與X的活動數(shù)相同。那么在Y中用活動1取代活動k得到Y(jié)'，因?yàn)閑1≤ek，所以Y'中活動也是兼容的，即Y'也是最優(yōu)解，這就說明A總存在一個以活動1開始的最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)25/86當(dāng)選擇活動1后，原問題就變成了在A'中找兼容活動的子問題。如果X為原問題的一個最優(yōu)解，而X'=X-{1}不是A'的一個最優(yōu)解，說明A'能夠找到的一個更優(yōu)解Y'，Y'中的兼容活動個數(shù)多于X'，這樣將活動1加入Y'后就得到A的一個更有解Y，Y中兼容活動個數(shù)多于X，這就與X是最優(yōu)解的假設(shè)相矛盾。26/86貪心選擇性質(zhì)從前面最優(yōu)子結(jié)構(gòu)性質(zhì)證明可以看出，每一步所做的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題，可以對貪心選擇次數(shù)用數(shù)學(xué)歸納法證明，這里不再詳述。27/86問題描述：給定一個含n個區(qū)間的集合intervals，每個區(qū)間的終點(diǎn)總是大于它的起點(diǎn)，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊，如區(qū)間{1，2}和{2，3}的邊界相互接觸，但沒有相互重疊。

例如，intervals={{1，2}，{2，3}，{3，4}，{1，3}}，移除區(qū)間{1，3}后剩下的區(qū)間沒有重疊，所以答案為1。

要求設(shè)計如下方法：def

eraseOverlapIntervals(self,intervals):7.2.2實(shí)戰(zhàn)—無重疊區(qū)間（LeetCode435★★）28/86解法1兩個相互不相交的區(qū)間就是兼容區(qū)間，采用前面活動安排問題Ⅰ的貪心方法求出intervals中最多兼容區(qū)間的個數(shù)ans，那么n-ans就是使剩余區(qū)間互不重疊需要移除區(qū)間的最小數(shù)量。稍有不同的是這里的區(qū)間起點(diǎn)和終點(diǎn)可能為負(fù)數(shù)，所以表示終點(diǎn)的preend初始值應(yīng)該設(shè)置為-∞而不是0。29/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals):3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按區(qū)間終點(diǎn)遞增排序7

ans=0

#表示兼容區(qū)間的個數(shù)8

preend=-INF #初始化為-∞9

for

i

in

range(0,n):10

if

intervals[i][0]>=preend:11

ans+=1 #兼容區(qū)間的個數(shù)增112

preend=intervals[i][1]13

return

n-ans30/86解法2同樣兩個相互不相交的區(qū)間就是保留的區(qū)間，為了使保留的區(qū)間最多，每次選擇的區(qū)間結(jié)尾越小，留給其他區(qū)間的空間就越大，就越能保留更多的區(qū)間，這樣采用的貪心選擇策略是優(yōu)先保留結(jié)尾小且不相交的區(qū)間。為此先將intervals按區(qū)間終點(diǎn)遞增排序，ans表示最少相交區(qū)間的個數(shù)（初始為0），每次選擇結(jié)尾最小且和前一個選擇的區(qū)間不相交的區(qū)間，一旦找不到這樣的區(qū)間時ans增1，最后返回ans。31/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals)->int:3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按區(qū)間終點(diǎn)遞增排序7

ans=0

#表示兼容區(qū)間的個數(shù)8

preend=-INF #初始化為-∞9

for

i

in

range(0,n):10

if

intervals[i][0]<preend:

#找到一個相交區(qū)間11

ans+=1 #移除該區(qū)間12

else:13

preend=intervals[i][1]

#重置preend14

return

ans32/86解法1：通過，執(zhí)行用時為168ms，內(nèi)存消耗為44.9MB。解法2：通過，執(zhí)行用時為176ms，內(nèi)存消耗為44.8MB。33/86有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，找到選中物品不僅能夠放到背包中而且價值最大的方案。與0/1背包問題的區(qū)別是這里的每個物品可以取一部分裝入背包。物品編號no01234w1020304050v2030664060W=1007.2.3求解背包問題34/86貪心策略：每次選擇單位重量價值最大的物品。序號i01234物品編號no31254w3010205040v6620306040v/w2.22.01.51.21.0x[0]=1bestv=66rw=rw-w[0]=70x[1]=1bestv=66+20=86rw=rw-w[1]=60x[2]=1bestv=86+30=116rw=rw-w[2]=40x[3]=0.8bestv=116+0.8*60=16435/861 defgreedly(g,W): #貪心算法2 globalx,bestv3 n=len(g)4 g.sort() #按v/w遞減排序5 x=[0]*n #存放最優(yōu)解向量6 bestv=0 #存放最大價值,初始為07 rw=W #背包中能裝入的余下重量36/868 i=09 whilei<nandg[i].w<rw: #物品i能夠全部裝入時循環(huán)10 x[i]=1 #裝入物品i11 rw-=g[i].w #減少背包中能裝入的余下重量12 bestv+=g[i].v #累計總價值13 i+=1 #繼續(xù)循環(huán)14 ifi<nandrw>0: #當(dāng)余下重量大于015 x[i]=rw/g[i].w #將物品i的一部分裝入16 bestv+=x[i]*g[i].v #累計總價值1737/8618 defknap(g,W): #求解背包問題19 greedly(g,W)20 print("求解結(jié)果") #輸出結(jié)果21 forjinrange(0,len(g)):22 ifx[j]==1:print("選擇%d[%d,%d]物品的比例是1" %(g[j].no,g[j].w,g[j].v))23 elifx[j]>0:print("選擇%d[%d,%d]物品的比例是%.1f" %(g[j].no,g[j].w,g[j].v,x[j]))24 print("總價值=%d"%(bestv))38/86程序驗(yàn)證物品編號no01234w1020304050v203066406039/86排序算法sort()的時間復(fù)雜性為O(nlog2n)，while循環(huán)的時間為O(n)。所以算法的時間復(fù)雜度為O(nlog2n)。算法分析40/867.2.4實(shí)戰(zhàn)—雪糕的最大數(shù)量（LeetCode1833★★）問題描述：商店中新到n支雪糕，用數(shù)組costs表示雪糕的價格，Tony一共有coins的現(xiàn)金，他想要買盡可能多的雪糕。

設(shè)計一個算法求Tony用coins現(xiàn)金能夠買到的雪糕的最大數(shù)量，可以按任意順序購買雪糕。

例如，costs={1，3，2，4，1}，coins=7，可以買下標(biāo)為0、1、2、4的雪糕，總價為1+3+2+1=7，答案為4。

要求設(shè)計如下方法：public

int

maxIceCream(int[]

costs,

int

coins)

{}41/86解類似背包問題，采用的貪心策略是優(yōu)先選擇價格小的雪糕，這樣使得剩余金額盡可能的多，將來能夠做的決策方案也就相應(yīng)變多。為此先將costs遞增排序，然后從前向后處理，能夠買的雪糕則買下。42/861 class

Solution:2

def

maxIceCream(self,

costs,

coins)

->

int:3

costs.sort()

#默認(rèn)遞增排序4

ans=05

rc=coins

#剩余的金額（從coins開始）6

for

i

in

range(0,len(costs)):7

if

costs[i]<=rc:

#可以買則買該雪糕8

ans+=19

rc-=costs[i]10

return

ans43/86問題描述：給定一組非負(fù)整數(shù)nums，重新排列每個數(shù)的順序（每個數(shù)不可拆分）使之組成一個最大的整數(shù)。由于輸出結(jié)果可能非常大，所以需要返回一個字符串而不是整數(shù)。

例如，nums={3，30，34，5，9}，輸出結(jié)果為"9534330"。

7.2.5實(shí)戰(zhàn)—最大數(shù)（LeetCode179★★）44/86解采用的貪心策略是將數(shù)字位越大的數(shù)字越排在前面，然后從前向后進(jìn)行合并即可。那么是不是直接將整數(shù)序列nums遞減排序后再從前向后合并呢？答案是錯誤的，例如nums=（50，2，1，9）遞減排序后為（50，9，2，1），合并后的結(jié)果是"50921"而不是正確的"95021"。為此改為這樣的排序方式，對于兩個整數(shù)a和b，將它們轉(zhuǎn)換為字符串s和t，若s+t>t+s，則a排在b的前面，例如，對于50和9兩個整數(shù)，轉(zhuǎn)換為字符串"50"和"9"，由于"950">"509"，所以"9">"50"。按照這種方式排序后，依次合并起來得到字符串a(chǎn)ns。如果ans的首字符為'0'，說明后面的元素均為0，則可直接返回"0"。45/861 import

functools2 class

Solution:3

def

largestNumber(self,

nums:

List[int])

->

str:4

a=[]5

for

x

in

nums:

#將nums轉(zhuǎn)換為字符串?dāng)?shù)組a6

a.append(str(x))7

def

cmp(s,t):

#按指定方式排序8

if

s+t<t+s:return

19

else:return

-146/8610

a.sort(key=functools.cmp_to_key(cmp))11

ans=""12

for

i

in

range(len(a)):ans+=a[i]

#依次合并得到ans13

if

ans[0]=='0':return

"0"

#處理特殊情況14

else:return

ans47/86問題描述：有面額分別是c0、c1、…、ck（c≥2，k為非負(fù)整數(shù)）的k+1種硬幣，每種硬幣個數(shù)可以看成無限多，求兌換A金額的最少硬幣個數(shù)。7.2.6求解零錢兌換問題48/86解

采用貪心法，貪心策略是盡可能選擇面額大的硬幣進(jìn)行兌換，例如，c=2，k=3，面額分別是{1，2，4，8}，A=23的兌換過程如下：選擇面額為8的硬幣，兌換的硬幣個數(shù)=A/8=2，剩余金額=23-2×8=7。選擇面額為4的硬幣，兌換的硬幣個數(shù)=A/4=1，剩余金額=7-4×1=3。選擇面額為2的硬幣，兌換的硬幣個數(shù)=A/2=1，剩余金額=3-2×1=1。選擇面額為1的硬幣，兌換的硬幣個數(shù)=A/1=1，剩余金額=1-1×1=0?？傆矌艂€數(shù)=2+1+1+1=549/861 defgreedly(c,k,A): #貪心算法2 ans=03 curm=2**k4 whileA>0:5 curs=A//curm #求面額為curm的硬幣個數(shù)6 ans+=curs #累計硬幣個數(shù)7 print("面額為%d的硬幣個數(shù)=%d"%(curm,curs))8 A-=curs*curm #剩余金額9 curm/=c;10 returnans1112 defsolve(c,k,A): #求解零錢兌換問題13 print("求解結(jié)果")14 print("兌換金額%d的最少硬幣個數(shù)=%d"%(A,greedly(c,k,A)))50/86A=23c=2k=3solve(c,k,A)程序驗(yàn)證51/867.3.1Prim算法構(gòu)造最小生成樹7.3求解圖問題Prim（普里姆）算法是一種構(gòu)造性算法。假設(shè)G=（V，E）是一個具有n個頂點(diǎn)的帶權(quán)連通圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T。52/86386174265054126338617426505412633861742650541263386174265054126353/86386174265054126338617426505412633861742650541263③3⑥6①1④4⑤2②60541263一棵最小生成樹54/86U={i|U[i]=1}V-U={j|U[j]=0}lowcost[j]closest[j]vkj算法中的符號：55/861 INF=0x3f3f3f3f2 defPrim(A,n,v): #Prim算法3 T=[] #存放最小生成樹4 lowcost=[INF]*n5 U=[0]*n6 closest=[0]*n7 forjinrange(0,n): #初始化lowcost和closest數(shù)組8 lowcost[j]=A[v][j]9 closest[j]=v10 U[v]=1 #源點(diǎn)加入U56/8611 foriinrange(1,n): #找出(n-1)個頂點(diǎn)12 mincost,k=INF,-113 forjinrange(0,n): #在(V-U)中找離U最近的頂點(diǎn)k14 ifU[j]==0andlowcost[j]<mincost:15 mincost=lowcost[j]16 k=j #k記錄最近頂點(diǎn)的編號17 T.append([closest[k],k,mincost]) #產(chǎn)生最小生成樹的一條邊18 U[k]=1 #頂點(diǎn)k加入U19 forjinrange(0,n): #修改數(shù)組lowcost和closest20 ifU[j]==0andA[k][j]<lowcost[j]:21 lowcost[j]=A[k][j]22 closest[j]=k23 returnT【算法分析】Prim()算法中有兩重for循環(huán)，所以時間復(fù)雜度為O(n2)。57/86Prim算法是一種貪心算法，如何理解Prim算法的最優(yōu)子結(jié)構(gòu)性質(zhì)呢？10332210312(a)一個帶權(quán)連通圖32210312(b)子問題58/86采用反證法證明Prim算法滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。證明：如果采用Prim算法求出原問題的生成樹T是最小生成樹，選擇第一條邊(v，a)后得到相應(yīng)的子問題，假設(shè)該子問題采用Prim算法求出的生成樹T1（T=(v，a)∪T1）不是最小的，而是最小生成樹為T2，則(v，a)∪T2得到原問題的一棵不同于T的更小的最小生成樹，用T是原問題的最小生成樹矛盾。最優(yōu)子結(jié)構(gòu)性質(zhì)即證。32210312(b)子問題59/86貪心選擇性質(zhì)證明。證明：k=1時，由前面最優(yōu)子結(jié)構(gòu)性質(zhì)證明可以得出命題是成立的。命題7.1對于任意正整數(shù)k<n，存在一棵最小生成樹T包含Prim算法前k步選擇的邊。60/86ek=(il，ik)e'UV-Uilikxy假設(shè)算法進(jìn)行了k-1步，生成樹的邊為e1，e2，…，ek-1，這些邊的k個頂點(diǎn)構(gòu)成集合U，并且存在G的一棵最小生成樹T包含這些邊。算法第k步選擇了頂點(diǎn)ik，則ik到U中頂點(diǎn)的邊的權(quán)值最小，設(shè)這條邊為ek=(il，ik)。假設(shè)最小生成樹T不含有邊ek，將ek添加到T中形成一個回路，如下圖所示，這個回路一定有連接U與V-U中頂點(diǎn)的邊e'，用ek替換e'得到樹T'，即T'=(T-{e'})∪{ek}。61/86則T'也是一棵生成樹，包含邊e1，e2，…，ek-1，ek，并且T'所有邊權(quán)值和更?。ǔ莈'與ek的權(quán)相同），與T為一棵最小生成樹矛盾，命題7.1即證。ek=(il，ik)e'UV-Uilikxy62/86當(dāng)命題7.1成立時，k=n-1即選擇了n-1條邊，此時U包含G中所有頂點(diǎn)，由Prim算法構(gòu)造的T=（U，TE）就是G的最小生成樹。命題7.1對于任意正整數(shù)k<n，存在一棵最小生成樹T包含Prim算法前k步選擇的邊。63/867.3.2Kruskal算法構(gòu)造最小生成樹Kruskal（克魯斯卡爾）算法按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹。假設(shè)G=(V，E)是一個具有n個頂點(diǎn)e條邊的帶權(quán)連通無向圖，T=(U，TE)是G的最小生成樹。64/863861742650541263(a)一個帶權(quán)連通圖38617426505412633861742650541263386174265054126365/86386174265054126338617426505412633861742650541263③3⑥6①1④4②2⑤60541263一棵最小生成樹66/86首先，U中包含全部頂點(diǎn)，TE為空，看成是由n個連通分量構(gòu)成的圖，每個連通分量中只有一個頂點(diǎn)，當(dāng)考慮一條邊(u，v)時，若u和v屬于兩個不同的連通分量，則加入該邊不會出現(xiàn)回路，否則會出現(xiàn)回路。這里每個連通分量就是并查集中的子集樹。用數(shù)組E存放圖G中的所有邊，按權(quán)值遞增排序，再從頭到尾依次考慮每一條邊，若可以加入則選擇該邊作為最小生成樹的一條邊，否則舍棄該邊。67/86#UFS并查集類參見第2章2.10.2節(jié)1～23的代碼1 INF=0x3f3f3f3f2 defKruskal(A,n): #Kruskal算法3 T=[] #存放最小生成樹4 E=[] #邊集5 foriinrange(0,n): #由A下三角部分產(chǎn)生的邊集E6 forjinrange(0,i):7 ifA[i][j]!=0andA[i][j]!=INF:8 E.append([i,j,A[i][j]])9 E.sort(key=itemgetter(2)) #按邊權(quán)值遞增排序10 ufs=UFS()

#定義并查集對象11 ufs.Init(n)

#初始化并查集12 k,j=0,0 #k表示當(dāng)前構(gòu)造生成樹的邊數(shù)68/8613 whilek<n-1: #生成的邊數(shù)小于n-1時循環(huán)14 u1,v1=E[j][0],E[j][1] #取一條邊(u1,v1)15 sn1,sn2=ufs.Find(u1),ufs.Find(v1) #兩個頂點(diǎn)所屬的集合編號16 ifsn1!=sn2: #添加該邊不會構(gòu)成回路17 T.append([u1,v1,E[j][2]]) #產(chǎn)生最小生成樹的一條邊18 k+=1 #生成邊數(shù)增119 ufs.Union(sn1,sn2) #將sn1和sn2兩個頂點(diǎn)合并20 j+=1 #遍歷下一條邊21 returnT69/86【算法分析】排序時間為O(elog2e)，while循環(huán)是在e條邊中選取n-1條邊，最壞情況下執(zhí)行e次，Union的執(zhí)行時間為O(log2n)，所以上述Kruskal算法構(gòu)造最小生成樹的時間復(fù)雜度為O(elog2e)?！綤ruskal算法的正確性證明】和Prim算法一樣都是貪心算法，其正確性證明與Prim算法類似，這里不再詳述。70/86問題描述：給定一個points數(shù)組，表示二維平面上的一些點(diǎn)，其中

points[i]={xi，yi}。連接兩個點(diǎn){xi，yi}和{xj，yj}的費(fèi)用為它們之間的曼哈頓距離即|xi-xj|+|yi-yj|。

求將所有點(diǎn)連接的最小總費(fèi)用，只有任意兩點(diǎn)之間有且僅有一條簡單路徑時才認(rèn)為所有點(diǎn)都已連接。

例如，points={{0，0}，{2，2}，{3，10}，{5，2}，{7，0}}，答案為20。

7.3.3實(shí)戰(zhàn)—連接所有點(diǎn)的最小費(fèi)用（LeetCode1584★★）71/86解法1：Prim算法本題給定的n個點(diǎn)看成是一個完全無向圖，邊的權(quán)值為對應(yīng)兩個點(diǎn)的曼哈頓距離，問題轉(zhuǎn)化為求最小生成樹的長度（最小生成樹中所有邊的權(quán)值和）。解法2：Kruskal算法Prim：執(zhí)行用時為704ms，內(nèi)存消耗為15.3MB。Kruskal：執(zhí)行用時為1172ms，內(nèi)存消耗為96.9MB。？60%和15.8%72/867.3.4Dijkstra算法求單源最短路徑設(shè)G=(V，E)是一個帶權(quán)有向圖，所有邊的權(quán)值為正數(shù)，給定一個源點(diǎn)v，求v到圖中其他頂點(diǎn)的最短路徑長度。Dijkstra（狄克斯特拉）算法把圖中頂點(diǎn)集合V分成兩組，第1組為已求出最短路徑的頂點(diǎn)集合（用S表示），初始時S中只有一個源點(diǎn)v，第2組為其余未求出最短路徑的頂點(diǎn)集合（用U表示）。每求得一條最短路徑v，…，u，就將u加入到集合S中（重復(fù)n-1次），直到全部頂點(diǎn)都加入到S中。73/86在向S中添加頂點(diǎn)u時，對于U中的每個頂點(diǎn)j，如果頂點(diǎn)u到頂點(diǎn)j有邊（權(quán)值為wuj），且原來從頂點(diǎn)v到頂點(diǎn)j的路徑長度（Dvj）大于從頂點(diǎn)v到頂點(diǎn)u的路徑長度（Dvu）與wuj之和，Dvj>Dvu+wuj，則將v

…

u→j的路徑作為v到j(luò)的新最短路徑，即Dvj=min(Dvj，Dvu+wuj)。vjuDvuwujDvj有一條邊有一條路徑Dvj=min(Dvj，cvu+wuj)74/86vjuA[u][j]松馳操作：dist[j]=min(dist[j],dist[u]+A[u][j])dist[u]dist[j]帶權(quán)有向圖用鄰接矩陣A表示dist[i]表示從源點(diǎn)v到頂點(diǎn)i的目前最短路徑長度75/861 defDijkstra(A,n,v): #Dijkstra算法2 globaldist3 dist=[0]*n4 S=[False]*n5 foriinrange(0,n):6 dist[i]=A[v][i] #距離初始化7 S[v]=True #源點(diǎn)v放入S中76/868 foriinrange(0,n-1): #循環(huán)n-1次9 u,mindis=-1,INF10 forjinrange(0,n): #選取U中具有最小距離的頂點(diǎn)u11 ifnotS[j]anddist[j]<mindis:12 u=j13 mindis=dist[j]14 ifu==-1:break15 S[u]=True #頂點(diǎn)u加入S中16 forjinrange(0,n): #修改U中的頂點(diǎn)的距離17 ifnotS[j]andA[u][j]!=0andA[u][j]<INF:18 dist[j]=min(dist[j],dist[u]+A[u][j])【算法分析】Dijkstra()算法中時間復(fù)雜度為O(n2)77/86Dijkstra算法的正確性證明轉(zhuǎn)換為證明以下命題成立。命題7.2Dijkstra算法中當(dāng)頂點(diǎn)u添加的S中時，dist[u]等于從源點(diǎn)v到u的最短路徑長度D[v，u]（D[i，j]表示圖中從頂點(diǎn)i到j(luò)的真實(shí)最短路徑長度）。證明：假設(shè)對于V中的某個頂點(diǎn)t，dist[t]>D[v,t]，并設(shè)u是算法中添加到S中的第一個滿足dist[u]>D[v,u]的頂點(diǎn)。因?yàn)榇嬖趶脑袋c(diǎn)v到u的最短路徑P，考慮當(dāng)u添加到S的時刻，令z是此時不在S中的P路徑上的第一個頂點(diǎn)。令y是路徑P中z的前一個頂點(diǎn)（可能有y=v）。78/86dist[u]>D[v,u]dist[z]=D[v,z]vuzPSyu是下一個選擇，因此dist[u]≤dist[z]第一個“不正確”的頂點(diǎn)dist[y