【正文】 evalue[j]結束是否dgevalue[i].value dgevalue[j].valuej++是i++ 15 函數(shù)之間的調(diào)用關系圖 五．測試數(shù)據(jù)及運行結果 16 1．正常測試數(shù)據(jù)及運行結果 17 非正常測試數(shù)據(jù) 及運行結果 18 六．調(diào)試情況，設計技巧及體會 通過此次課程設計，我更深刻地理解了最小生成樹問題，知道如何在 n 個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。closedge[i].lowcost kk = closedge[i].lowcost。 開始創(chuàng)建標記數(shù)組并初始化將所有權值按從小到大排序利用標記數(shù)組判斷是否形成環(huán)是否掃描完全部線路輸出權值最小線路形成最小生成樹結束否是否 12 ※ LocateVex（）節(jié)點位置函數(shù)： 13 ※ Minimum()權值比較函數(shù)： 開始int i,j iclosedge[i].lowcost!= 0amp。在此系統(tǒng)中 ， N 是你所需要輸入的城市個數(shù)。之后，從網(wǎng)的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。 開始 標志頂點 1 加入 U 集合 尋找滿足邊的一個頂點在 U,另一個頂點在 V 的最小邊 形成 n1 條邊的生成樹 頂點 k 加入 U 修改由頂點 k 到其他頂點邊的權值 結束 得到 最小生成樹 11 ※ MiniSpanTree_KRSL()克魯斯卡爾算法： 基本思想： 假 設 WN=（ V, {E}）是一個含有 N 個頂點的連通網(wǎng)。在此系統(tǒng)中， N 是你所需要輸入的城市個數(shù)。顯然，在算法執(zhí)行結束時， TV=V， 而 TE 是 E 的一個子集。 dgevalue[j].ch2 = ch2。 ch2 = dgevalue[i].ch2。 dgevalue[i].ch1 = dgevalue[j].ch1。 dgevalue[j].value = temp。 j++) { if(dgevalue[i].value dgevalue[j].value) { temp = dgevalue[i].value。 i++) 7 { for(j=i。 for(i=0。 double temp。 } } } } void Sortdge(Dgevalue amp。 j。 endl。 p2 = bj[LocateVex(G,dgevalue[i].ch2)]。 i。 Sortdge(dgevalue,G)。 i。 int bj[MAX_VERTEX_NUM]。 } ※ 最小生成樹 kruscal 算法 ： void MiniSpanTree_KRSL(MGraph G,Dgevalue amp。 j = i。amp。 i。 double k = 1000。 closedge[j].lowcost= [k][j].adj。 j。 closedge[k].lowcost = 0。 cout 城市 closedge[k].adjvex與城市 [k]連接。 i。 } } closedge[k].lowcost = 0。 j++) //輔助數(shù)組初始化 { if(j != k) { closedge[j].adjvex = u。 for(j=0。 Closedge closedge。 cout\b\b endl。amp。dgevalue[j].ch2!=[i]) coutdgevalue[j].ch2。j++) if(dgevalue[j].ch1==[i]amp。 for(j=0。i。 } } 5 ※鄰接表的輸出： void Adjacency_List(MGraph G,Dgevalue dgevalue) //用鄰接表儲存數(shù)據(jù) { int i,j。 else cout[i][j].adj 。 j。 i。 } ※臨接矩陣的輸出： void Adjacency_Matrix(MGraph G) //用鄰接矩陣存儲數(shù)據(jù) { int i,j。 [j][i].adj = [i][j].adj。 j = LocateVex(G,dgevalue[k].ch2)。++k) { cin dgevalue[k].ch1 dgevalue[k].ch2 dgevalue[k].value。 for(k=0。++j) { [i][j].adj=MAX。++i)//初始化數(shù)組 for(j=0。 for(i=0。i。 cout請輸入各個城市名稱 (分別用一個字符代替 )： 。 cout請輸入城市個數(shù)及其之間的可連接線路數(shù)目： 。 G,Dgevalue amp。) break。 if(y==39。 } coutendl是否繼續(xù)？ y/n:。 default: 4 cout您的輸入有誤 !。 MiniSpanTree_KRSL(G,dgevalue)。 break。 cinu。 case 3: cout普里姆算法最經(jīng)濟的連接方案為 :endl。 Adjacency_List(G,dgevalue)。 break。 switch(s) { case 1: cout用鄰接矩陣存儲為： endl。) { cout請選擇菜單： endl。 whi