貪心法求最小生成樹算法

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

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