最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、ooxx 最小生成樹(shù)實(shí)現(xiàn)各個(gè)城市之間的網(wǎng)絡(luò)線路 第19頁(yè) 共20頁(yè)最小生成樹(shù)實(shí)現(xiàn)各個(gè)城市之間的網(wǎng)絡(luò)線路 學(xué)生姓名：oo 指導(dǎo)老師：xx摘 要:最小生成樹(shù)是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應(yīng)用，在圖中對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，最小生成樹(shù)就是在所有生成樹(shù)中總的代價(jià)最小的生成樹(shù)。本課程設(shè)計(jì)是以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu),分別采用prim和kruskal算法求最小生成樹(shù)。kruskal算法和prim算法是求最小生成樹(shù)的常用算法它們分別適用于稠密圖和稀疏圖。最小生成樹(shù)的應(yīng)用非常的廣，如礦井通風(fēng)設(shè)計(jì)和改造最優(yōu)化方面以及如何搭建最短的網(wǎng)絡(luò)線纜, 構(gòu)建造價(jià)最低的通訊網(wǎng)絡(luò) 。關(guān)鍵詞：最小生成樹(shù)；krus

2、kal算法；prim算法，abstract the minimum cost spanning tree data structure is an important application of chinese, in the picture for n vertex even tongwang can create many different spanning tree, minimum spanning tree is in all spanning tree in the total cost of the minimum spanning tree. this course is

3、designed as a figure of the adjacency matrix storage structure, we adopt prim and kruskal minimum spanning tree algorithm. kruskal prim algorithm and minimum spanning tree algorithm is used for the algorithm respectively applicable and sparsely populated. minimum spanning tree is very wide applicati

4、on in mines, such as the ventilation design and modification and optimization in how to set up the shortest cable network, constructing the lowest cost of communications networkkeywords: minimum cost spanning tree；kruskal algorithm；prim algorithm 1 引 言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)和信息管理與信息系統(tǒng)專業(yè)的必修課之一，是一門(mén)綜合性的專業(yè)基礎(chǔ)課。本

5、課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的實(shí)現(xiàn)算法，如線性表、棧、隊(duì)列、樹(shù)和二叉樹(shù)，圖、檢索和排序等，并對(duì)性能進(jìn)行分析和比較，內(nèi)容非常豐富。本課程設(shè)計(jì)我們要解決的問(wèn)題是圖最小生成樹(shù)問(wèn)題。要用到圖的先相關(guān)數(shù)據(jù)結(jié)構(gòu)和求最小生成樹(shù)的兩種數(shù)據(jù)結(jié)構(gòu)算法普里姆算法和克魯斯卡爾算法，以及儲(chǔ)存圖的邊和點(diǎn)的鄰接矩陣。本課程設(shè)計(jì)要解決的問(wèn)題構(gòu)造連通網(wǎng)的最小生成樹(shù) ,我們首先要做的是創(chuàng)建一個(gè)鄰接矩陣，用以來(lái)存儲(chǔ)圖，然后我們要想好怎樣利用普里姆算法和克魯斯卡爾算法來(lái)構(gòu)造最小生成樹(shù)。把這兩種算法寫(xiě)入主函數(shù)，調(diào)試好程序。最后寫(xiě)好報(bào)告。2 設(shè)計(jì)目的與任務(wù)2.1課程設(shè)計(jì)目的 本課程設(shè)計(jì)的目的是了解并掌握數(shù)據(jù)結(jié)構(gòu)與算

6、法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)。 2.2課程設(shè)計(jì)的任務(wù) 問(wèn)題描述: 已知一個(gè)無(wú)向連通網(wǎng)表示n個(gè)城市以及城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的線路，賦于邊上的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)點(diǎn)的連通網(wǎng)能建立許多不同的生成樹(shù)，每一棵生成樹(shù)都可以是一個(gè)通信網(wǎng)。我們要選擇一棵生成樹(shù)，使總的耗費(fèi)最小。 3 設(shè)計(jì)方案3.1需求分析1)建立一個(gè)圖，其存儲(chǔ)方式可以采用鄰接矩陣形式，需要定義兩個(gè)數(shù)

7、組，一個(gè)存儲(chǔ)頂點(diǎn)，一個(gè)存儲(chǔ)邊，存儲(chǔ)邊的數(shù)組表明節(jié)點(diǎn)間的連通關(guān)系和邊的權(quán)值；。2)利用普里姆算法和克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)3)按順序輸出生成樹(shù)中各條邊以及它們的權(quán)值。3.2數(shù)據(jù)結(jié)構(gòu)分析構(gòu)造最小生成樹(shù)的方法：最初生成樹(shù)為空，即沒(méi)有一個(gè)結(jié)點(diǎn)和一條邊，首先選擇一個(gè)頂點(diǎn)作為生成樹(shù)的根，然后每次從不在生成樹(shù)中的邊中選擇一條權(quán)值盡可能小的邊，為了保證加入到生成樹(shù)中的邊不會(huì)造成回路，與該邊鄰接的兩個(gè)頂點(diǎn)必須一個(gè)已經(jīng)在生成樹(shù)中，一個(gè)則不在生成樹(shù)中，若網(wǎng)中有n個(gè)頂點(diǎn)（這里考慮的網(wǎng)是一個(gè)連通無(wú)向圖），則按這種條件選擇n-1邊就可以得到這個(gè)網(wǎng)的最小生成樹(shù)了。詳細(xì)的過(guò)程可以描述為：設(shè)置2個(gè)集合，u集合中的元素是在

8、生成樹(shù)中的結(jié)點(diǎn)，v-u集合中的元素是不在生成樹(shù)中的頂點(diǎn)。首先選擇一個(gè)作為生成樹(shù)根結(jié)點(diǎn)的頂點(diǎn)，并將它放入u集合，然后在那些一端頂點(diǎn)在u集合中，而另一端頂點(diǎn)在v-u集合中的邊中找一條權(quán)最小的邊，并把這條邊和那個(gè)不在u集合中的頂點(diǎn)加入到生成樹(shù)中，即輸出這條邊，然后將其頂點(diǎn)添加到u集合中，重復(fù)這個(gè)操作n-1次。1) 抽象數(shù)據(jù)類型(adt)如下：adt graph 數(shù)據(jù)對(duì)象v：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系r：r=vr vr=|v,w屬于v且p(v,w),(v,w)表示從v到w的弧，謂詞p(v,w)定義了弧的意義或信息 基本操作：(1) creatgraph(&g,v,vr)；初

9、始條件：v是圖的頂點(diǎn)集，vr是圖中弧的集合。操作結(jié)果：按v和vr的定義構(gòu)造圖g。(2) locatevex(g, u)； 初始條件：圖g存在,u和g中頂點(diǎn)有相同的特征。操作結(jié)果：若g中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中的位置；否則返回其他信息。(3) destorygraph(&u)；初始條件：圖g存在。操作結(jié)果：銷(xiāo)毀圖g。(4) getvex(g, v)；初始條件：圖g存在，v是圖中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的值。(5) nextadjvex(g, v, w)；初始條件：圖g存在，v是圖中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回

10、“空”。(6) bfstraverse(g, visit( )；初始條件：圖g存在，visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit( )失敗，則操作失敗。2) 存儲(chǔ)結(jié)構(gòu)typedef struct int adj; int weight;adjmatrixmaxmax;typedef struct djmatrix arc; int vexnum, arcnum; mgraph;3) 流程圖，如下圖所示：2、用prim算法求解最小生成樹(shù)3、用kruskal算法最最小生成樹(shù)功能選擇開(kāi) 始1、建立鄰接矩陣結(jié) 束 圖3

11、.1 流程圖3.3最小生成樹(shù)的算法分析在該函數(shù)中主要有五段代碼塊，分別是主函數(shù)代碼塊、鄰接矩陣定義模塊代碼、創(chuàng)建鏈接矩陣模塊代碼、最小生成樹(shù)prim算法及代價(jià)模塊代碼與最小生成樹(shù)kruskal算法及代價(jià)模塊代碼，五段代碼塊分別有著不同的作用，共同滿足了課題所需要實(shí)現(xiàn)的功能。 1) 主函數(shù)模塊代碼algraph gra; mgraph_l g; int i,d,g2020;char a=a; d=creatmgraph_l(g); vnode v;coutendl注意：若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)endl 最小生成樹(shù)不存在,則顯示為非法值endlendl;cout菜單endlendl

12、;cout0、顯示該圖的鄰接矩陣endl;cout1、最小生成樹(shù)prim算法及代價(jià)endl;int s; char y=y;while(y=y) cout請(qǐng)選擇菜單：s; switch(s)case 0: cout鄰接矩陣顯示如下：endl; ljjzprint(g); break; case 1: for(i=0;i!=g.vexnum;+i) for(intj=0;j!=g.vexnum;+j) gi+1j+1=g.arcsij.adj; coutprim:endl; prim(g,d); break; coutendly; if(y=n) break; 該主函數(shù)用一個(gè)循環(huán)語(yǔ)句，來(lái)執(zhí)行其它

13、的函數(shù)的功能。從鍵盤(pán)輸入頂點(diǎn)數(shù)和邊數(shù)上限，再調(diào)用定義連接矩陣的函數(shù)，后輸出創(chuàng)建連接矩陣的信息，再調(diào)用creatmgraph（）函數(shù)，接著進(jìn)入菜單，然后再選擇輸入一個(gè)數(shù)確定是要輸出連接矩陣還是最小生成樹(shù)及代價(jià)，最后選擇輸入確定字母y或n確定是否繼續(xù)。 2) 鄰接矩陣定義模塊代碼typedef struct arccell int adj; char *info;arccell,adjmatrix2020;typedef struct char vexs20; adjmatrix arcs; int vexnum,arcnum;mgraph_l;int localvex(mgraph_l g,ch

14、ar v) int i=0; while(g.vexsi!=v) +i; return i;用typedef struct定義連接矩陣，通過(guò)二維數(shù)組來(lái)存儲(chǔ)連接矩陣，并設(shè)定參數(shù)的最大值為20。3) 創(chuàng)建鏈接矩陣模塊代碼 int creatmgraph_l(mgraph_l &g) char v1,v2; int i,j,w; cout創(chuàng)建無(wú)向圖（城市分布圖）endl;cout 請(qǐng)輸入圖g頂點(diǎn)（城市）和?。ㄟ叄┑膫€(gè)數(shù):(4 6)不包括“()”g.vexnumg.arcnum; for(i=0;i!=g.vexnum;+i) cout輸入頂點(diǎn)（城市）ig.vexsi; for(i=0;i!=g.ve

15、xnum;+i)for(j=0;j!=g.vexnum;+j) g.arcsij.adj=int_max; g.=null; for(int k=0;k!=g.arcnum;+k) cout輸入一條邊依附的頂點(diǎn)（城市）和權(quán)（距離）:(a b 3)不包括“()”v1v2w; i=localvex(g,v1); j=localvex(g,v2); g.arcsij.adj=w; g.arcsji.adj=w; cout圖g鄰接矩陣創(chuàng)建成功！endl; return g.vexnum;該語(yǔ)句是從鍵盤(pán)輸入頂點(diǎn)數(shù)和邊數(shù)，輸入頂點(diǎn)和權(quán)值，通過(guò)循環(huán)語(yǔ)句的調(diào)用，最后調(diào)用creatmgra

16、ph_l（）創(chuàng)建連接矩陣 。4) 最小生成樹(shù)prim算法及代價(jià)模塊代碼 int prim(int gmax,int n) int lowcostmax,prevexmax; int i,j,k,min;int sum=o; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) /形成n-1條邊的生成樹(shù) min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)&(lowcostj!=0)min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k

17、-1,min); sum+=min; lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) lowcostj=gkj; prevexj=k; printf(n); cout最少生成樹(shù)的代價(jià):; coutsum; return 0; 該語(yǔ)句運(yùn)用一系列的循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的，利用前面的創(chuàng)建好的鏈接矩陣，通過(guò)各邊權(quán)值的比較，最后調(diào)用prim()函數(shù)，實(shí)現(xiàn)最小生成樹(shù)的生成，同時(shí)運(yùn)用sum把最小生成樹(shù)各邊權(quán)值相加得到最小生成樹(shù)的代價(jià)。5) 最小生成樹(shù)kruskal算法及代價(jià)模塊代碼 void minispantree(mgrapha *d)/生成最小生成樹(shù) int i, j

18、, n, m, sum=0; int k = 1;int parentm; edge edgesm;for ( i = 1; i vexnum; i+) for (j = i + 1; j vexnum; j+) if (d-arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = d-arcij.weight; k+;sort(edges, d);for (i = 1; i arcnum; i+) parenti = 0; printf(最小生成樹(shù)為:n);for (i = 1; i arcnum; i+)/核心部分 n

19、 = find(parent, edgesi.begin); m = find(parent, edgesi.end);if (n != m) parentn = m; printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);sum=sum+edgesi.weight;cout最少生成樹(shù)的代價(jià):; coutsum.該語(yǔ)句運(yùn)用一系列的循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的，利用前面的創(chuàng)建好的鏈接矩陣，通過(guò)各邊權(quán)值的比較，最后調(diào)用minispantree ()函數(shù)，實(shí)現(xiàn)最小生成樹(shù)的生成，同時(shí)運(yùn)用sum把最小生成樹(shù)各邊權(quán)值相加得到最小生成樹(shù)的代價(jià)。4 調(diào)試分析與體會(huì)在我

20、組的集體努力下，課程設(shè)計(jì)終于完成，由于我們對(duì)數(shù)據(jù)結(jié)構(gòu)和c語(yǔ)言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫(xiě)程序的過(guò)程中出現(xiàn)了一些問(wèn)題。對(duì)于打字有時(shí)粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我們的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)完滿完工。1、問(wèn)題一：求出圖中的最小值 現(xiàn)象：求出的最小值是0原因：圖中沒(méi)有連通的兩個(gè)頂點(diǎn)之間的權(quán)值賦值為02、問(wèn)題二：求最小生成樹(shù)時(shí)，else語(yǔ)句需再調(diào)用一個(gè)函數(shù) 現(xiàn)象：對(duì)某些二叉樹(shù)能求出最小生成樹(shù)，但不能普遍適應(yīng)原因：對(duì)于找最小生成樹(shù)邊的各種可能沒(méi)有考慮全面，代碼才沒(méi)有廣泛的適應(yīng)性3、問(wèn)題三：兩個(gè)頂點(diǎn)之間的邊是否是最小生成樹(shù)的邊現(xiàn)象：代碼的功能不能分辨出是

21、否是最小生成樹(shù)的邊原因：把簡(jiǎn)單的代碼寫(xiě)的很復(fù)雜，從而雜亂無(wú)章出現(xiàn)錯(cuò)誤。5 運(yùn)行結(jié)果將程序員錄入后,讓其運(yùn)行。將會(huì)出現(xiàn)一個(gè)菜單的界面，執(zhí)行各種操作均有其對(duì)應(yīng)的代碼。要執(zhí)行何種操作只需輸入對(duì)應(yīng)的指令即可進(jìn)行，在每步操作后均會(huì)有相應(yīng)的提示。操作簡(jiǎn)單方便實(shí)用，下面即為一些操作的示意圖。運(yùn)行程序后出界面，運(yùn)行結(jié)果如下圖所示：圖5.1 初界面圖圖中有1-3三個(gè)選項(xiàng)，可選取其中的一個(gè)選項(xiàng)進(jìn)行操作。選取選項(xiàng)1進(jìn)行操作，運(yùn)行結(jié)果如下圖所示：圖5.2 建立鄰接矩陣運(yùn)行圖依據(jù)提示，分別輸入無(wú)向圖的頂點(diǎn)個(gè)數(shù)與弧的個(gè)數(shù)，然后依次輸入各個(gè)頂點(diǎn)所對(duì)應(yīng)的符號(hào)及與各個(gè)頂點(diǎn)相關(guān)聯(lián)的弧與權(quán)值，存在鄰接矩陣中。若選取選項(xiàng)3，運(yùn)行結(jié)果

22、如下圖所示： 圖5.3 求的最小生成樹(shù)運(yùn)行圖圖中顯示了求得的最小生成樹(shù)所對(duì)應(yīng)的邊、權(quán)值與最小生成樹(shù)的代價(jià)。結(jié) 論經(jīng)過(guò)我們不懈的努力我們終于完成了本次課程設(shè)計(jì)，通過(guò)這次課程設(shè)計(jì)，我感覺(jué)到要真正做出一個(gè)程序并不很容易，但只要用心去做，總會(huì)有收獲，特別是當(dāng)我遇到 一個(gè)問(wèn)題，想辦法去解決，最后終于找到方法時(shí)，心里的那份喜悅之情真是難以形容。編寫(xiě)程序中遇到問(wèn)題再所難免，應(yīng)耐心探究其中的原因，從出現(xiàn)問(wèn)題的地方起，并聯(lián)系前后程序，仔細(xì)推敲，逐個(gè)排查。直到最終搞清為止。我們本次做的是圖的做小生成樹(shù)問(wèn)題，深刻的體會(huì)到它的實(shí)用性。通過(guò)本次課程設(shè)計(jì)我們發(fā)現(xiàn)我們對(duì)于c語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)還有很多地方不知道，今后需要努力學(xué)習(xí)

23、。參考文獻(xiàn)1 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）m. 北京：清華大學(xué)出版社,1997.2 譚浩強(qiáng). c程序設(shè)計(jì)（第三版）m. 北京：清華大學(xué)出版社，2005.1. 3 二霍紅衛(wèi)算法設(shè)計(jì)與分析西安西安電子科技大學(xué)出版社，2005.113-127.4 陳杰.計(jì)算機(jī)專業(yè)課程設(shè)計(jì)中的需求分析j.集美大學(xué)學(xué)報(bào)，2009，10(2)：8992.5 高一凡. 數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析m . 西安:西安電子科技大學(xué)出版社, 20026 pascal之父niklaus wirth 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 科學(xué)出版社 20017 蘇運(yùn)霖 數(shù)據(jù)結(jié)構(gòu)與算法 中南工業(yè)大學(xué)出版社 20028 徐寶文 李志 譚浩強(qiáng)c 程序

24、設(shè)計(jì)語(yǔ)言(第二版新版) c+程序設(shè)計(jì) 機(jī)械工業(yè)出版社 20049 shaffer 數(shù)據(jù)結(jié)構(gòu)與算法分析(c+版、java版) 電子工業(yè)出版社 1999附錄：程序清單#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20#define max 20#define m 20typedef struct arccellint adj;char *info;arccell,adjmatrix2020;typedef struct char vexs20;adjmatrix ar

25、cs; int vexnum,arcnum;mgraph;int localvex(mgraph g,char v) int i=0; while(g.vexsi!=v) +i; return i;void ljjzprint(mgraph g) int i,j,n=0; printf(建立的鄰接矩陣如下：n); printf(n); printf( _n); for(i=0;i!=g.vexnum;i+) for(j=0;j!=g.vexnum;j+) if(j=0)printf( ); printf(%d,g.arcsij.adj);printf( );n+; if(n=g.vexnum)

26、 printf(n);n=0; printf( _n);int creatmgraph(mgraph &g)char v1,v2; int i,j,w; printf(建立鄰接矩陣:n); printf(請(qǐng)輸入圖g頂點(diǎn)（城市）和?。ㄟ叄┑膫€(gè)數(shù):); scanf(%d,&g.vexnum); scanf(%d,&g.arcnum); printf(輸入所有頂點(diǎn):); for(i=0;ig.vexsi; for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij.adj=int_max; g.=null; printf(輸入所有邊

27、及依附的頂點(diǎn)（城市）和權(quán)（距離）:n);for(int k=0;kv1v2w; i=localvex(g,v1); j=localvex(g,v2); g.arcsij.adj=w; g.arcsji.adj=w; ljjzprint(g); printf(圖g鄰接矩陣創(chuàng)建成功！n); return g.vexnum; int visitedmax; int we;typedef struct arcnode int adjvex; struct arcnode *nextarc; char *info; arcnode;typedef struct vnode char data; arcn

28、ode *firstarc; vnode,adjlist;typedef struct/圖的定義 adjlist verticesmax; int vexnum, arcnum; int kind; algraph;int prim(int gmax,int n) /最小生成樹(shù)prim算法 int lowcostmax, prevexmax; int i,j,k,min; int sum=0; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) min=inf; k=0; for(j=2;j=n;j+) if

29、(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min;lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) owcostj=gkj;prevexj=k; printf(n); cout最少生成樹(shù)的代價(jià):; coutarcnum,&d-vexnum);for (i = 1; i vexnum; i+)/初始化圖for ( j = 1; j vexnum; j+) d-arcij.adj = d-arcji.adj = 0;for (

30、 i = 1; i arcnum; i+)/輸入邊和權(quán)值printf(n請(qǐng)輸入有邊的2個(gè)頂點(diǎn)); scanf(%d %d,&n,&m);while(n d-vexnum | m d-vexnum)printf(輸入的數(shù)字不符合要求 請(qǐng)重新輸入:); scanf(%d%d,&n,&m); d-arcnm.adj = d-arcmn.adj = 1; getchar();printf(n請(qǐng)輸入%d與%d之間的權(quán)值:, n, m); scanf(%d,&d-arcnm.weight);printf(鄰接矩陣為:n);for ( i = 1; i vexnum; i+)for ( j = 1; j v

31、exnum; j+)printf(%d ,d-arcij.adj); printf(n);void sort(edge edges,mgrapha *d)/對(duì)權(quán)值進(jìn)行排序int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight) swapn(edges, i, j);printf(權(quán)排序之后的為:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);v

32、oid swapn(edge *edges,int i, int j)/交換權(quán)值 以及頭和尾int temp; temp = edgesi.begin;edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end;edgesi.end = edgesj.end; edgesj.end = temp;temp = edgesi.weight; edgesi.weight = edgesj.weight;edgesj.weight = temp;void minispantree(mgrapha *d)/生成最小生成樹(shù)int i, j, n, m,sum=0; int k = 1;int parentm; edge edgesm;for ( i = 1; i vexnum; i+)for (j = i +