第5章 貪心算法

第5章貪心算法1VisualFoxPro主要內(nèi)容5.1貪心算法概述5.2貪心算法的理論基礎(chǔ)5.3刪數(shù)字問題5.4背包問題5.5覆蓋問題5.6圖的著色問題5.7遍歷問題5.8最小生成樹5.9哈夫曼編碼2VisualFoxPro5.1貪心算法概述5.1.1貪心算法

有一艘大船準(zhǔn)備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i個貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多箱的貨物。

這個問題可以作為最優(yōu)化問題進(jìn)行描述：設(shè)存在一組變量xi，其可能取值為0或1。如xi為0，則貨箱i將不被裝上船；如xi為1，則貨箱i將被裝上船。我們的目的是找到一組xi，使它滿足限制條件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。相應(yīng)的優(yōu)化函數(shù)是ni=∑wixi取極值。滿足限制條件的每一組xi都是一個可行解，能使ni=∑wixi取得極大值的方案是最優(yōu)解。3VisualFoxPro找硬幣問題假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某個顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，拿出的硬幣個數(shù)是最少的。這里，使用了這樣的找硬幣方法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪心算法。4VisualFoxPro

貪心算法（也稱貪心策略）總是作出在當(dāng)前看來是最好的選擇。如上面的找硬幣問題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動態(tài)規(guī)劃算法來解。但我們看到，用貪心算法更簡單，更直接且解題效率更高。這利用了問題本身的一些特性。貪心算法在求解最優(yōu)化問題時，從初始階段開始，每一個階段總是作一個使局部最優(yōu)的貪心選擇，不斷把將問題轉(zhuǎn)化為規(guī)模更小的子問題。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。這樣處理，對大多數(shù)優(yōu)化問題來說能得到最優(yōu)解，但也并不總是這樣。從求解效率來說，貪心算法比動態(tài)規(guī)劃更高，且不存在空間限制的影響。另外，對一些NP完全問題或規(guī)模很大的優(yōu)化問題，可通過仿貪心算法能得到很好的近世解，而用動態(tài)規(guī)劃根本無法解。5VisualFoxPro5.1.2.貪心算法的基本思想

貪心算法的基本思想是通過一系列選擇步驟來構(gòu)造問題的解，每一步都是對當(dāng)前部分解的一個擴(kuò)展，直至獲得問題的完整解。所做的每一步選擇都必須滿足：(1)可行的：必須滿足問題的約束。(2)局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部選擇。(3)不可取消:選擇一旦做出，在后面的步驟中就無法改變了。貪心算法是通過做一系列的選擇來給出某一問題的最優(yōu)解，對算法的每一個決策點(diǎn)，做一個當(dāng)時（看起來）是最佳的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。6VisualFoxPro5.2貪心算法的理論基礎(chǔ)

“矩陣胚”理論

“矩陣胚”理論是一種能夠確定貪心算法何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。定義

矩陣胚是一個序?qū)=[S，I]

，其中S是一個有序非空集合，I是S的一個非空子集，成為S的一個獨(dú)立子集。7VisualFoxPro如果M是一個N×M的矩陣的話，即:

若M是無向圖G的矩陣胚的話，則S為圖的邊集，I是所有構(gòu)成森林的一組邊的子集。如果對S的每一個元素X（X∈S）賦予一個正的權(quán)值W（X），則稱矩陣胚M(jìn)=（S，I）為一個加權(quán)矩陣胚。8VisualFoxPro適宜于用貪心算法來求解的許多問題都可以歸結(jié)為在加權(quán)矩陣胚中找一個具有最大權(quán)值的獨(dú)立子集的問題，即給定一個加權(quán)矩陣胚，M=（S，I），若能找出一個獨(dú)立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨(dú)立子集所包含，那么A為最優(yōu)子集，也是一個最大的獨(dú)立子集。矩陣胚理論對于我們判斷貪心算法是否適用于某一復(fù)雜問題是十分有效的。

9VisualFoxPro對給定的n位高精度正整數(shù),去掉其中k(k<n)個數(shù)字后，按原左右次序?qū)⒔M成一個新的正整數(shù)，使得剩下的數(shù)字組成的新數(shù)最大。操作對象是一個可以超過有效數(shù)字位數(shù)的n位高精度數(shù),存儲在數(shù)組a中。每次刪除一個數(shù)字,選擇一個使剩下的數(shù)最大的數(shù)字作為刪除對象。之所以選擇這樣“貪心”的操作,是因為刪k個數(shù)字的全局最優(yōu)解包含了刪一個數(shù)字的子問題的最優(yōu)解。當(dāng)k=1時,在n位整數(shù)中刪除哪一個數(shù)字能達(dá)到最大的目的?從左到右每相鄰的兩個數(shù)字比較:若出現(xiàn)增,即左邊小于右邊,則刪除左邊的小數(shù)字。若不出現(xiàn)減,即所有數(shù)字全部升序,則刪除最右邊的大數(shù)字。5.3刪數(shù)字問題10VisualFoxPro當(dāng)k>1(當(dāng)然小于n),按上述操作一個一個刪除。刪除一個達(dá)到最大后,再從頭即從串首開始,刪除第2個,依此分解為k次完成。若刪除不到k個后已無左邊小于右邊的增序,則停止刪除操作,打印剩下串的左邊n-k個數(shù)字即可(相當(dāng)于刪除了若干個最右邊的數(shù)字)。下面我們給出采用貪心算法的刪數(shù)字問題的部分c語言代碼：11VisualFoxPro

while(k>x&&m==0){i=i+1;if(a[i-1]<a[i])/*出現(xiàn)遞增,刪除遞增的首數(shù)字*/{printf("%d",a[i-1]);for(j=i-1;j<=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x統(tǒng)計刪除數(shù)字的個數(shù)*/i=0;/*從頭開始查遞增區(qū)間*/}if(i==n-x-1)/*已無遞增區(qū)間,m=1脫離循環(huán)*/m=1;}printf("\n刪除后所得最大數(shù):");for(i=1;i<=n-k;i++)/*打印剩下的左邊n-k個數(shù)字*/printf("%d",a[i-1]);

12VisualFoxPro

5.4背包問題已知n種物品和一個可容納c重量的背包，物品i的重量為wi，產(chǎn)生的效益為pi。裝包時物品可拆，即可只裝每種物品的一部分。顯然物品i的一部分放入背包可產(chǎn)生的效益為，這里。問如何裝包，使所得整體效益最大。(1)算法設(shè)計應(yīng)用貪心算法求解。每一種物品裝包，由可以整個裝入，也可以只裝一部分，也可以不裝。約束條件：目標(biāo)函數(shù)：要使整體效益即目標(biāo)函數(shù)最大，按單位重量的效益非增次序一件件物品裝包，直至某一件物品裝不下時，裝這種物品的一部分把包裝滿。解背包問題貪心算法的時間復(fù)雜度為O(n)。

13VisualFoxPro幾個背包實例1.w=[100,10,10]，p=[20,15,15]，c=105;2.w=[10,20]，p=[5,100]，c=25;3.w=[20,15,15]，p=[40,25,25]，c=304.w=[2,4,6,7]，p=[6,10,12,13],c=11;14VisualFoxPro物品可拆背包問題C程序設(shè)計代碼如下：for(i=1;i<=n-1;i++)/*對n件物品按單位重量的效益從大到小排序*/for(j=i+1;j<=n;j++)if(p[i]/w[i]<p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw為背包還可裝的重量*/for(i=1;i<=n;i++){if(w[i]>cw)break;x[i]=1.0;/*若w(i)<=cw,整體裝入*/cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)>cw,裝入一部分x(i)*/s=s+p[i]*x[i];15VisualFoxProprintf("裝包：");/*輸出裝包結(jié)果*/for(i=1;i<=n;i++)if(x[i]<1)break;elseprintf("\n裝入重量為%5.1f的物品.",w[i]);if(x[i]>0&&x[i]<1)printf("\n裝入重量為%5.1f的物品百分之%5.1f.",w[i],x[i]*100);printf("\n所得最大效益為：%7.1f",s);16VisualFoxPro作業(yè)：一個數(shù)列由n個正整數(shù)組成，對該數(shù)列進(jìn)行一次操作：去除其中兩項a、b，添加一項a*b+1。經(jīng)過n-1次操作后該數(shù)列剩一個數(shù)a，試求a的最大值。17VisualFoxPro二分圖是一個無向圖，它的n個頂點(diǎn)可二分為集合A和集合B，且同一集合中的任意兩個頂點(diǎn)在圖中無邊相連（即任何一條邊都是一個頂點(diǎn)在集合A中，另一個在集合B中）。當(dāng)且僅當(dāng)B中的每個頂點(diǎn)至少與A中一個頂點(diǎn)相連時，A的一個子集A‘覆蓋集合B（或簡單地說，A’是一個覆蓋）。覆蓋A‘的大小即為A’中的頂點(diǎn)數(shù)目。當(dāng)且僅當(dāng)A‘是覆蓋B的子集中最小的時，A’為最小覆蓋。二分覆蓋問題類似于集合覆蓋問題?？梢詫⒓细采w問題轉(zhuǎn)化為二分覆蓋問題（反之亦然），即用A的頂點(diǎn)來表示S1,.,Sk，B中的頂點(diǎn)代表U中的元素。當(dāng)且僅當(dāng)S的相應(yīng)集合中包含U中的對應(yīng)元素時，在A與B的頂點(diǎn)之間存在一條邊。5.5覆蓋問題18VisualFoxPro集合覆蓋問題為NP-復(fù)雜問題。由于集合覆蓋與二分覆蓋是同一類問題，二分覆蓋問題也是NP-復(fù)雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪心算法尋找一種快速啟發(fā)式方法。一種可能是分步建立覆蓋A‘，每一步選擇A中的一個頂點(diǎn)加入覆蓋。頂點(diǎn)的選擇利用貪心準(zhǔn)則：從A中選取能覆蓋B中還未被覆蓋的元素數(shù)目最多的頂點(diǎn)。我們給出覆蓋問題的貪心算法的偽代碼，可以證明：(1)當(dāng)且僅當(dāng)初始的二分圖沒有覆蓋時，算法找不到覆蓋；(2)啟發(fā)式方法可能找不到二分圖的最小覆蓋。19VisualFoxPro算法描述如下：

m=0;//當(dāng)前覆蓋的大小

對于A中的所有i，Malloc[i]=Degree[i]

對于B中的所有i，Cov[i]=false

while(對于A中的某些i,Malloc[i]>0){

設(shè)v是具有最大的New[i]的頂點(diǎn)；

C[m++]=v;

for(所有鄰接于v的頂點(diǎn)j){

if(!Cov[j]){

Cov[j]=true;

對于所有鄰接于j的頂點(diǎn)，使其New[k]減1

}}}20VisualFoxProif(有些頂點(diǎn)未被覆蓋)失敗

else找到一個覆蓋該算法的時間復(fù)雜度取決于數(shù)據(jù)的存儲方式，若使用鄰接矩陣，則需花(n2)的時間來尋找圖中的邊，若用鄰接鏈表，則需(n+e)的時間。故覆蓋算法總的復(fù)雜性為O(n2)或O(n+e)21VisualFoxPro

圖著色問題是其實對應(yīng)很多應(yīng)用的例子，假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的貪心算法進(jìn)行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點(diǎn)，不相容活動間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會場數(shù)。)

活動安排問題：設(shè)有n個活動a1,a2,…,an,每個活動都要求使用同一資源，而同一時間內(nèi)只允許一個活動使用這一資源。已知活動ai要求使用該資源的起始時間為si，結(jié)束時間為fi，且si<=fi。要求在a1,a2,…,an中選出最大的相容活動子集。兩活動ai,aj(i≠j)相容是指：5.6圖的著色問題22VisualFoxPro例：n=4,活動：a1a2a3a4si：4218fi：74510貪心選擇策略：按結(jié)束時間從早到晚安排活動，每次選擇與已選出的活動相容的結(jié)束時間盡可能早的活動。局部最優(yōu)性：每次為資源留下盡可能多的時間以容納其它活動。該算法的時間復(fù)雜性：Θ(nlogn)。使用貪心算法求解圖的著色問題并不總能得到最優(yōu)解,只保證得到近似最優(yōu)解。其實，頂點(diǎn)的編號方法決定了這種算法的結(jié)果。至少存在一種編號方法使這個貪心算法能得到最優(yōu)解。23VisualFoxProvoidcolor_up(intnodes)//著色函數(shù){

inti,j,k=1;

int*color;

color=(int*)malloc((sizeof(int))*(nodes+1));//初始化顏色數(shù)

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

color[i]=0;

color[1]=1;

do

{

for(i=2;i<=nodes;i++)

{

if(color[i]>0)continue;

下面給出圖的著色問題的c語言程序:24VisualFoxPro

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

if((color[j]==k)&&(graph[i-1][j-1]!=0))break;if(j==i)color[i]=k;

}

j=2;

while((color[j]>0)&&(j<=nodes))j++;

k++;

}while(j<=nodes);

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

printf("node%dcolor:%d\n",i,color[i]);}25VisualFoxPro馬的遍歷問題。在n×n方格的棋盤上，從任意指定方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。在這里僅以8×8的棋盤為例。算法初步描述：首先這是一個搜索問題，運(yùn)用深度優(yōu)先搜索進(jìn)行求解。算法如下：(1)輸入初始位置坐標(biāo)x,y；(2)初始化c:如果c>64輸出一個解，返回上一步驟c--(x,y)←c計算(x,y)的八個方位的子結(jié)點(diǎn)，選出那此可行的子結(jié)點(diǎn)循環(huán)遍歷所有可行子結(jié)點(diǎn)，c++重復(fù)25.7遍歷問題26VisualFoxPro顯然（２）是一個遞歸調(diào)用的過程，大致如下：voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(I=0;i<8;++i){tx=hn[i].x;//hn[]保存八個方位子結(jié)點(diǎn)ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調(diào)用s[tx][ty]=0;}}27VisualFoxPro這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當(dāng)８×８時解是非常之多的，用天文數(shù)字形容也不為過，這樣一來求解的過程就非常慢，并且出一個解也非常慢。怎么才能快速地得到部分解呢？其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的算法。在每個結(jié)點(diǎn)對其子結(jié)點(diǎn)進(jìn)行選取時，優(yōu)先選擇‘出口’最小的進(jìn)行搜索，‘出口’的意思是在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個數(shù)，也就是‘孫子’結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法.28VisualFoxPro

其實這種求解就是利用了貪心算法，它對整個求解過程的局部做最優(yōu)調(diào)整，它只適用于求較優(yōu)解或者部分解，而不能求最優(yōu)解。這樣的調(diào)整方法叫貪心策略，至于什么問題需要什么樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運(yùn)用到了上面的貪心策略之后求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個算法提出的時候世界上還沒有計算機(jī)，這種方法完全可以用手工求出解來，其效率可想而知。29VisualFoxPro下面我們給出馬踏棋盤問題的c代碼（８×８）：intways_out(intx,inty)//計算結(jié)點(diǎn)出口多少{inti,count=0,tx,ty;if(x<0||y<0||x>=N||y>=N||s[x][y]>0)return-1;//-1表示該結(jié)點(diǎn)非法或者已經(jīng)跳過了for(i=0;i<8;++i){tx=x+dx[i];ty=y+dy[i];if(tx<0||ty<0||tx>=N||ty>=N)continue;if(s[tx][ty]==0)++count;}returncount;}30VisualFoxProvoidsortnode(h_node*hn,intn)//采用簡單排序法，因為子結(jié)點(diǎn)數(shù)最多只有8{//按結(jié)點(diǎn)出口進(jìn)行排序inti,j,t;h_nodetemp;for(i=0;i<n;++i){for(t=i,j=i+1;j<n;++j)if(hn[j].waysout<hn[t].waysout)t=j;if(t>i){temp=hn[i];hn[i]=hn[t];hn[t]=temp;}}}31VisualFoxProvoiddfs(intx,inty,intcount)//修改后的搜索函數(shù){inti,tx,ty;h_nodehn[8];if(count>N*N){output_solution();return;}for(i=0;i<8;++i)//求子結(jié)點(diǎn)和出口{hn[i].x=tx=x+dx[i];hn[i].y=ty=y+dy[i];hn[i].waysout=ways_out(tx,ty);}sortnode(hn,8);

32VisualFoxProfor(i=0;hn[i].waysout<0;++i);//不考慮無用結(jié)點(diǎn)for(;i<8;++i){tx=hn[i].x;ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);s[tx][ty]=0;}}33VisualFoxPro5.8最小生成樹

假設(shè)已知一無向連通圖G=(V,E)，其加權(quán)函數(shù)為w:E→R，我們希望找到圖G的最小生成樹。后文所討論的兩種算法都運(yùn)用了貪心方法，但在如何運(yùn)用貪心法上卻有所不同。下列的算法GENERNIC-MIT正是采用了貪心算法，每步形成最小生成樹的一條邊。算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊(u,v)添加到集合A中，其添加條件是A∪{(u,v)}仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因為可以安全地把它添加到A中而不會破壞上述條件。GENERNIC-MIT(G,W)1.A←?2.whileA沒有形成一棵生成樹3do找出A的一條安全邊(u,v);4.A←A∪{(u,v)};5.returnA34VisualFoxPro定理5.1設(shè)圖G(V,E)是一無向連通圖，且在E上定義了相應(yīng)的實數(shù)值加權(quán)函數(shù)w，設(shè)A是E的一個子集且包含于G的某個最小生成樹中，割(S,V-S)是G的不妨害A的任意割且邊(u,v)是穿過割(S,V-S)的一條輕邊，則邊(u,v)對集合A是安全的。下面介紹兩個算法：Kruskal算法和Prim算法(1)Kruskal算法

Kruskal算法是直接基于上面中給出的一般最小生成樹算法的基礎(chǔ)之上的。該算法找出森林中連結(jié)任意兩棵樹的所有邊中具有最小權(quán)值的邊(u,v)作為安全邊，并把它添加到正在生長的森林中。設(shè)C1和C2表示邊(u,v)連結(jié)的兩棵樹。因為(u,v)必是連C1和其他某棵樹的一條輕邊，所以由推論2可知(u,v)對C1是安全邊。Kruskal算法同時也是一種貪心算法，因為算法每一步添加到森林中的邊的權(quán)值都盡可能小

35VisualFoxProKruskal算法的實現(xiàn)類似于計算連通支的算法。它使用了分離集合數(shù)據(jù)結(jié)構(gòu)以保持?jǐn)?shù)個互相分離的元素集合。通過FIND-SET(v)來確定兩結(jié)點(diǎn)u和v是否屬于同一棵樹，通過操作UNION來完成樹與樹的聯(lián)結(jié)。MST-KRUSKAL(G,w)1.A←?2.for每個結(jié)點(diǎn)vV[G]3.doMAKE-SET(v)4.根據(jù)權(quán)w的非遞減順序?qū)的邊進(jìn)行排序5.for每條邊(u,v)?E，按權(quán)的非遞減次序6.doifFIND-SET(u)≠FIND-SET(v)7.thenA←A∪{(u,v)}8.UNION(u,v)9returnA36VisualFoxProKruskal算法在圖G=(V,E)上的運(yùn)行時間取決于分離集合這一數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)。我們采用在分離集合中描述的按行結(jié)合和通路壓縮的啟發(fā)式方法來實現(xiàn)分離集合森林的結(jié)構(gòu)，這是由于從漸近意義上來說，這是目前所知的最快的實現(xiàn)方法。(2)Prim算法Prim算法的特點(diǎn)是集合A中的邊總是只形成單棵樹。因為每次添加到樹中的邊都是使樹的權(quán)盡可能小的邊，因此上述策略也是貪心的。有效實現(xiàn)Prim算法的關(guān)鍵是設(shè)法較容易地選擇一條新的邊添加到由A的邊所形成的樹中，在下面的偽代碼中，算法的輸入是連通圖G和將生成的最小生成樹的根r。在算法執(zhí)行過程中，不在樹中的所有結(jié)點(diǎn)都駐留于優(yōu)先級基于key域的隊列Q中。對每個結(jié)點(diǎn)v，key[v]是連接v到樹中結(jié)點(diǎn)的邊所具有的最小權(quán)值；按常規(guī)，若不存在這樣的邊則key[v]=∞。域p[v]說明樹中v的“父母”。

37VisualFoxPro在算法執(zhí)行中，GENERIC-MST的集合A隱含地滿足：A={(v,p[v])|v?V-{r}-Q}當(dāng)算法終止時，優(yōu)先隊列Q為空，因此G的最小生成樹A滿足:A={(v,p[v])|v?V-{r}}MST-PRIM(G,w,r)1.Q←V[G]2.for每個u?Q3.dokey[u]←∞4.key[r]←05.p[r]←NIL6.whileQ≠?7.dou←EXTRACT-MIN(Q)8.for每個v?Adj[u]9.doifv?Qandw(u,v)<key[v]10.thenp[v]←u11.key[v]←w(u,v)38VisualFoxProPrim算法的性能分析Prim算法的性能取決于我們?nèi)绾螌崿F(xiàn)優(yōu)先隊列Q。若用二叉堆來實現(xiàn)Q,我們可以使用過程BUILD-HEAP來實現(xiàn)第1-4行的初始化部分，其運(yùn)行時間為O(V)。循環(huán)需執(zhí)行|V|次，且由于每次EXTRACT-MIN操作需要O(㏒V)的時間，所以對EXTRACT-MIN的全部調(diào)用所占用的時間為O(V㏒V)。第8-11行的for循環(huán)總共要執(zhí)行O(E)次，這是因為所有鄰接表的長度和為2|E|。在for循環(huán)內(nèi)部，第9行對隊列Q的成員條件進(jìn)行測試可以在常數(shù)時間內(nèi)完成，這是由于我們可以為每個結(jié)點(diǎn)空出1位(bit)的空間來記錄該結(jié)點(diǎn)是否在隊列Q中，并在該結(jié)點(diǎn)被移出隊列時隨時對該位進(jìn)行更新。第11行的賦值語句隱含一個對堆進(jìn)行的DECREASE-KEY操作，該操作在堆上可用0(㏒V)的時間完成。因此，Prim算法的整個運(yùn)行時間為O(V㏒V+E㏒V)=O(E㏒V)，從漸近意義上來說，它和實現(xiàn)Kruskal算法的運(yùn)行時間相同。

39VisualFoxPro通過使用Fibonacci堆，Prim算法的漸近意義上的運(yùn)行時間可得到改進(jìn)。在Fibonacci堆中我們己經(jīng)說明，如果|V|個元素被組織成Fibonacci堆，可以在O(㏒V)的平攤時間內(nèi)完成EXTRACT-MIN操作，在O(1)的平攤時間里完成DECREASE-KEY操作（為實現(xiàn)第11行的代碼），因此，若我們用Fibonacci堆來實現(xiàn)優(yōu)先隊列Q，Prim算法的運(yùn)行時間可以改進(jìn)為O(E+V㏒V)。40VisualFoxPro5.9哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的