貪心法求最小生成樹算法

貪心策略求最小生成樹問題設(shè)G=(V,E)是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價，在G的所有生成樹中，代價最小的生成樹稱為最小生成樹(MinimalSpanningTrees)。最小生成樹問題至少有兩種合理的貪心策略：(1)最近頂點策略：任選一個頂點，并以此建立起生成樹，每一步的貪心選擇是簡單地把不在生成樹中的最近頂點添加到生成樹中。Prim算法就應(yīng)用了這個貪心策略,它使生成樹以一種自然的方式生長，即從任意頂點開始，每一步為這棵樹添加一個分枝，直到生成樹中包含全部頂點。1717(e)U={A,F,C,D,E}(e)U={A,F,C,D,E}cost={(E,B)12}(f)U={A,F,C,D,E,B}cost={(A,B)34,(F,E)26}設(shè)圖G中頂點的編號為0?n-1.Prim算法如下：算法7.4——Prim算法初始化兩個輔助數(shù)組lowcost和adjvex；U={u0};輸出頂點u0; //將頂點u0加入生成樹中重復(fù)執(zhí)行下列操作n-1次3.1在lowcost中選取最短邊，取adjvex中對應(yīng)的頂點序號k；輸出頂點k和對應(yīng)的權(quán)值；U=U+{k}；調(diào)整數(shù)組lowcost和adjvex；上述偽代碼中，數(shù)組closest[j]是j(jlV-S)在S中的領(lǐng)接頂點，它與j在S中的其它頂點相比較有c[j][cloest[j]]<=c[j][k]olowest[j啲值就是c[j][cloest[j]]。在算法執(zhí)行過程中，先找出V-S中是lowest值最小的頂點j,然后根據(jù)數(shù)組closest選取邊(j,cloest[j])，最后將j添加到S

中，并對closest和lowest作必要的修改。程序運行結(jié)果為：連通帶權(quán)圖的矩陣為，599999999999939999599999999999939999564999999992999999996包999955999999995=99936.99999994269999Pf5算法最小生成權(quán)寸注邊複序如衛(wèi)fi63623請按任意鍵繼續(xù).利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。設(shè)連通網(wǎng)中有n個頂點，則第一個進行初始化的循環(huán)語句需要執(zhí)行n-1次，第二個循環(huán)共執(zhí)行n-1次，內(nèi)嵌兩個循環(huán)，其一是在長度為n的數(shù)組中求最小值，需要執(zhí)行n-1次，其二是調(diào)整輔助數(shù)組，需要執(zhí)行n-1次，所以，Prim算法的時間復(fù)雜度為O(n2)。2)最短邊策略：設(shè)G=(V，E)是一個無向連通網(wǎng)，令T=(U，TE)是G的最小生成樹。最短邊策略從TE={}開始，每一次貪心選擇都是在邊集E中選取最短邊(u,v)，如果邊(u,v)加入集合TE中不產(chǎn)生回路，則將邊(u,v)加入邊集TE中，并將它在集合E中刪去。Kruskal算法就應(yīng)用了這個貪心策略，它使生成樹以一種隨意的方式生長，先讓森林中的樹木隨意生長，每生長一次就將兩棵樹合并，到最后合并成一棵樹。實現(xiàn)算法Kruskal需要準備兩個數(shù)據(jù)結(jié)構(gòu)：(1)最小堆MinHeap,按權(quán)的遞增順序查看的邊的序列可以看做是一個優(yōu)先隊列，它的優(yōu)先級為邊權(quán)；2)并查集UnionFind,主要包括Union(a,b)和Find(v)兩個基本運算：Union(a,b)將兩個連通分支a和b連接起來，所得的結(jié)果為A或B；Find(v)返貨U總包含頂點v的連通分支的名字。這個運算用來確定某條邊的兩個端點所屬的連通分支。(d)(f)(e)(f)算法7.5——Kruskal算法初始化：U=v； TE={}；循環(huán)直到T中的連通分量個數(shù)為12.1在E中尋找最短邊(u,v);2.2如果頂點u、v位于T的兩個不同連通分量，則將邊(u,v)并入TE；將這兩個連通分量合為一個；2.3E=E-{(u，v)}；當(dāng)圖的邊數(shù)為e時,Kruskal算法所需的計算時間是?。當(dāng)匚_八一〔時,Kruskal算法比Prim算法差，但當(dāng)= U時，Kruskal算法卻比Prim算法好得多。程序運行結(jié)果為：狂通帶權(quán)圖所有邊的兩端頂詆叔分別為:u：l,weight：6□.u：2Li:1,weight:l,u：3u：l,weight：5,u：411=2,weight：5：3u：2,ueight:3,u：5u：3,weight：5.s4u：3,weight：4,u：6it：3,weight:6,u汚u：4,weight：2小北li：5,weight:6j-u：6Kruskal算法最小生成樹選擇結(jié)果為；u：1,weight：1Au：3it：4,weight:2,u:Em2,weight：3：5it：3,weight:4,u：6u：2,weight：5,u：3請按任意鍵繼續(xù)???■Kruskal算法為了提高每次貪心選擇時查找最短邊的效率，可以先將圖G中的邊按代價從小到大排序，則這個操作的時間復(fù)雜度為O(elog2e),其中e為無向連通網(wǎng)中邊的個數(shù)。對于兩個頂點是否屬于同一個連通分量，可以用并查集的操作將其時間性能提高到O(n),所以,Kruskal算法的時間性能是O(elog2e)。實驗小結(jié)：通過這次實驗，我們深刻了解到貪心法的概念。貪心法(greedymethod)是把一個復(fù)雜問題分解為一系列較為簡單的局部最優(yōu)選擇,每一步選擇都是對當(dāng)前解的一個擴展,直到獲得問題的完整解。貪心法的典型應(yīng)用是求解最優(yōu)化問