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

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

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

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

3、，根是其本身。rank數(shù)組初始化0Find(x):查找x所在集合的代表元素。即查找根，確定x所在的集合，并路徑壓縮。Merge(x,y):檢查x與y是否在同一個集合，如果在同一個集合則返回假，否則按秩合并這兩個集合并返回真。2:主程序：intmain(){初始化；wh訂e(條件){接受命令；處理命令；}return0;}3：抽象數(shù)據(jù)類型圖的定義如下：ADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。數(shù)據(jù)關(guān)系R：R={VR}VR={

4、v,wWV且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧3

5、,w>的意義或信息}4：抽象數(shù)據(jù)類型樹的定義如下：ADTTree{數(shù)據(jù)對象D:D是具有相同特性數(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}7^0),則存在D-{root}的一個劃分Di,禺，???，幾(m>0),對任意jHk(lWj,kWin)有DjflDk二①，且對任意的I(lWiWm),惟一存在數(shù)據(jù)元素x^Di有〈root,Xi〉WH；(3)對應(yīng)于D-{root}的劃分，H-{

6、〈root,xi>,…，0),對任意jHk(lWj,kWm)有比nHk=0,且對任意I(lWiWm),Hi是Di上的二元關(guān)系，(Di,{HJ)是一棵符合本定義的樹，稱為跟root的子樹。5:本程序包括兩個模塊，調(diào)用關(guān)系比較簡單：(1)主程序模塊(2)帶權(quán)無向圖模塊。程序各模塊之間的調(diào)用關(guān)系如下：主程序模塊V帶權(quán)無向圖模塊一.詳細設(shè)計#include#include#includeusingnamespacestd;#defineMOD10

7、1#delineMAXN30intset[MAXN];intrank[MAXN];typedefstructMintree｛〃最小生成樹結(jié)構(gòu)體定義intx,y;intdis;JMintree;Mintreemap[MAXNJ,mst[MAXNJ;boolcmp(constMintreea^constMintreeb)｛returna.dis

8、r=x;while(set[r]!=r)r=set[rj;inti=x,j;while(i!=r)｛j=set[i];set[i]=r;i=j；｝〃路徑壓縮returnr;boolMerge(intx,inty){〃合并集合函數(shù)intfx=Find(x);intfy=Find(y);if(fx!=fy){〃兩端點不在一個集合，合并并返回真if(rank[fx]>rank[fy]){set[fyj=fx;}elseif(rank[fx]

9、turntrue;}returnfalse;〃兩端點原本在一個集合，返回假。}intmain(){intn,i,j,k,num;intf