最小生成樹問題_課程設(shè)計(jì)報(bào)告(編輯修改稿)
2025-04-09 17:15 本頁面
【文章內(nèi)容簡(jiǎn)介】 for(i=0。 i。 i++) { p1 = bj[LocateVex(G,dgevalue[i].ch1)]。 p2 = bj[LocateVex(G,dgevalue[i].ch2)]。 if(p1 != p2) { cout 城市 dgevalue[i].ch1與城市 dgevalue[i].ch2連接。 endl。 for(j=0。 j。 j++) { if(bj[j] == p2) bj[j] = p1。 } } } } void Sortdge(Dgevalue amp。 dgevalue,MGraph G)//對(duì) dgevalue中各元素按權(quán)值按從小到大排序 { int i,j。 double temp。 char ch1,ch2。 for(i=0。 i。 i++) 7 { for(j=i。 j。 j++) { if(dgevalue[i].value dgevalue[j].value) { temp = dgevalue[i].value。 dgevalue[i].value = dgevalue[j].value。 dgevalue[j].value = temp。 ch1 = dgevalue[i].ch1。 dgevalue[i].ch1 = dgevalue[j].ch1。 dgevalue[j].ch1 = ch1。 ch2 = dgevalue[i].ch2。 dgevalue[i].ch2 = dgevalue[j].ch2。 dgevalue[j].ch2 = ch2。 } } } } 主要函數(shù)的程序流程圖 ※ main（） 主 函數(shù) 開始CreateUDG()switch()Adjacency_Matrix()Adjacency_List()MiniSpanTree_KRSL()MiniSpanTree_PRIM()結(jié)束 8 ※ CreatUDG()建圖 函數(shù) 開始結(jié)束輸入城市個(gè)數(shù)及連接數(shù)目確定頂點(diǎn)在圖中的位置輸入線路及費(fèi)用輸入各城市名稱 ※ Adjacency_Matrix()鄰接矩陣輸出 函數(shù) 開始結(jié)束int i,ji[i][j].adj==MAX輸出0 輸出G . a r c s [ i ] [ j ] . a d ji++,j++是否是否 9 ※ Adjacency_List()鄰接表輸出函數(shù) 10 ※ MiniSpanTree_PRIM()普里姆算法： 基本思想： 假設(shè) WN=(V,{E})是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)， TV 是 WN 上最小生成樹中頂點(diǎn)的集合， TE 是最小生成樹中邊的集合。顯然，在算法執(zhí)行結(jié)束時(shí)， TV=V， 而 TE 是 E 的一個(gè)子集。在算法開始執(zhí)行時(shí)，TE 為空集， TV中只有一個(gè)頂點(diǎn)，因此，按普利姆算法構(gòu)造最小生成樹的過程為：在所有“其一個(gè)頂點(diǎn)已經(jīng)落在生成樹上，而另一個(gè)頂點(diǎn)尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n1 條邊為止。在此系統(tǒng)中， N 是你所需要輸入的城市個(gè)數(shù)。而每條邊的權(quán)值就是你所輸入的每?jī)蓚€(gè)城市之間的建設(shè)成本。 開始 標(biāo)志頂點(diǎn) 1 加入 U 集合 尋找滿足邊的一個(gè)頂點(diǎn)在 U,另一個(gè)頂點(diǎn)在 V 的最小邊 形成 n1 條邊的生成樹 頂點(diǎn) k 加入 U 修改由頂點(diǎn) k 到其他頂點(diǎn)邊的權(quán)值 結(jié)束 得到 最小生成樹 11 ※ MiniSpanTree_KRSL()克魯斯卡爾算法： 基本思想： 假 設(shè) WN=（ V, {E}）是一個(gè)含有 N 個(gè)頂點(diǎn)的連通網(wǎng)。則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有 n 棵樹的一個(gè)森林。之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n1 條邊為止。在此系統(tǒng)中 ， N 是你所需要輸入的城市個(gè)數(shù)。而每條邊的權(quán)值就是你所輸入的每?jī)蓚€(gè)城市之間的建設(shè)成本。 開始創(chuàng)建標(biāo)記數(shù)組并初始化將所有權(quán)值按從小到大排序利用標(biāo)記數(shù)組判斷是否形成環(huán)是否掃描完全部線路輸出權(quán)值最小線路形成最小生成樹結(jié)束否是否 12 ※ LocateVex（）節(jié)點(diǎn)位置函數(shù)： 13 ※ Minimum()權(quán)值比較函數(shù)： 開始int i,j iclosedge[i].lowcost!= 0amp。amp。closedge[i].lowcost kk = closedge[i].lowcost。 j = i。 結(jié)束，返回ji++是否 14 ※ Sortdge()權(quán)值排序函數(shù)： 開始int i,j ij交換d g e v a l u e [ i ] 和dgevalue[j]結(jié)束是否dgevalue[i].value dgevalue[j].valuej++是i++ 15 函數(shù)之間的調(diào)用關(guān)系圖 五．測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 16 1．正常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 17 非正常測(cè)試數(shù)據(jù) 及運(yùn)行結(jié)果 18 六．調(diào)試情況，設(shè)計(jì)技巧
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1