算法設(shè)計與分析報告-貪心法求最小生成樹

《算法設(shè)計與分析報告-貪心法求最小生成樹》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實用標(biāo)準(zhǔn)文案算法設(shè)計與分析——貪心法求最小生成樹一．問題描述1.可以用連通網(wǎng)來表示n個城市間可能設(shè)置的通信網(wǎng)絡(luò)，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的路線，邊的權(quán)值表示相應(yīng)的費(fèi)用。對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)。現(xiàn)在，我們要選擇這樣一棵生成樹，它使總的費(fèi)用最少，這棵樹就是最小生成樹。一棵生成樹的費(fèi)用就是樹上各邊的費(fèi)用之和。2.本程序的目的是要建設(shè)一個最經(jīng)濟(jì)的通信網(wǎng)，根據(jù)用戶輸入的網(wǎng)，輸出相應(yīng)的最小生成樹。在這里城市以及兩城市之間的費(fèi)用都用整型數(shù)來代替。3．程序執(zhí)行的命令包括：（1）利用克魯斯卡爾算法求最小生成樹。（2）構(gòu)造最小生成樹中的連通

2、分量。（3）權(quán)值應(yīng)存放在定義的數(shù)組中。（4）輸入城市個數(shù)。（5）輸出費(fèi)用最少的生成樹。（6）結(jié)束。4．測試數(shù)據(jù)用戶自定義輸入城市個數(shù)，輸入結(jié)束后回車即顯示生成的最小生成樹及最小開銷。二．概要設(shè)計1：抽象數(shù)據(jù)類型MFSet的定義：ADTMFSet{數(shù)據(jù)對象：若設(shè)S是MFSet型的集合，則它由n(n>0)個子集Si（i=1,2...,n）構(gòu)成，每個子集的成員代表在這個子集中的城市。數(shù)據(jù)關(guān)系：S1US2US3U...USn=S,Si包含于S（i=1,2,...n）Init(n):初始化集合，構(gòu)造n個集合，每個集合都是單成員，根是其本身。rank數(shù)組初始化0Find(x):查找x所在集合的代表元

3、素。即查找根，確定x所在的集合，并路徑壓縮。Merge(x,y):檢查x與y是否在同一個集合，如果在同一個集合則返回假，否則按秩合并這兩個集合并返回真。2：主程序：intmain(){初始化；while(條件){接受命令;處理命令;精彩文檔實用標(biāo)準(zhǔn)文案}return0;}3：抽象數(shù)據(jù)類型圖的定義如下：ADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。數(shù)據(jù)關(guān)系R：R={VR}VR={

4、v，w∈V且P（v，w），表示從v到w的弧，謂詞P（v，w）定義了弧的意義或信息}4：抽象數(shù)據(jù)類型樹的定義如下：ADTTree{數(shù)據(jù)對象D:D是具有相同

5、特性數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；若D僅含一個元素數(shù)據(jù)，則R為空集，否則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D-{root}≠，則存在D-{root}的一個劃分D1，D2，…，Dm（m>0），對任意j≠k（1≤j,k≤m）有Dj∩Dk=，且對任意的I（1≤i≤m），惟一存在數(shù)據(jù)元素xi∈Di有∈H；（3）對應(yīng)于D-{root}的劃分，H-{，…，}有惟一的一個劃分H1，H2，…，Hm（m＞0），對任意j≠k(1≤j，k≤m)有Hj∩Hk=，且對

6、任意I（1≤i≤m），Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹，稱為跟root的子樹。5:本程序包括兩個模塊，調(diào)用關(guān)系比較簡單：（1）主程序模塊（2）帶權(quán)無向圖模塊。程序各模塊之間的調(diào)用關(guān)系如下：主程序模塊帶權(quán)無向圖模塊三．詳細(xì)設(shè)計#include#include#include精彩文檔實用標(biāo)準(zhǔn)文案usingnamespacestd;#defineMOD101#defineMAXN30intset[MAXN];intrank[MAXN];typedefstructMintree{//最小生成樹結(jié)構(gòu)體定義intx,y

7、;intdis;}Mintree;Mintreemap[MAXN],mst[MAXN];boolcmp(constMintreea,constMintreeb){returna.dis

8、ge(intx,inty)精彩文檔實用標(biāo)準(zhǔn)文案{//合并集合函數(shù)intfx=Find(x);intfy=Find(y);if(fx!=fy){//兩端點不在一個集合，合并并返回真if(rank[fx]>rank[fy]){set[fy]=fx;}elseif(rank[fx]