算法設(shè)計(jì)與分析報(bào)告-貪心法求最小生成樹(shù)

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

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

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

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

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

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

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

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

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