構(gòu)造可以使n個(gè)城市連接最小生成樹

數(shù)據(jù)構(gòu)造課程設(shè)計(jì)說明書學(xué)院：信息科學(xué)與工程學(xué)院班級：計(jì)算機(jī)11-2完成人：姓名：學(xué)號：01050220姓名：學(xué)號：01050221指導(dǎo)教師：山東科技大學(xué)12課程設(shè)計(jì)任務(wù)書一、課程設(shè)計(jì)題目：構(gòu)造能夠使n個(gè)都市連接的最小生成樹二、課程設(shè)計(jì)應(yīng)解決的重要問題：（1）鄰接矩陣的構(gòu)造及其存儲（2）判斷與否能夠生成最小生成樹（3）克魯斯算法的設(shè)計(jì)（4）運(yùn)用克魯斯算法構(gòu)造最小生成樹時(shí)與否產(chǎn)生回路的判斷（5）界面的設(shè)計(jì)三、任務(wù)發(fā)出日期：-11-28課程設(shè)計(jì)完畢日期：-12

小組分工闡明小組編號35題目：構(gòu)造可使n個(gè)都市連接的最小生成樹小組分工狀況：王露：算法設(shè)計(jì)，voidKruskal()函數(shù)，voidset()函數(shù)，voidfind()函數(shù)，voidUnion()函數(shù)王煒程：voidcreat()函數(shù)，voidjudge()函數(shù)，intmain()函數(shù)；intmenu()函數(shù)，voiddisplay()函數(shù) 組長簽字：年月日指導(dǎo)教師對課程設(shè)計(jì)的評價(jià)成績：指導(dǎo)教師簽字：年月日

目錄重要問題------------------------------------------------------------------5基本規(guī)定------------------------------------------------------------------5算法基本思想描述------------------------------------------------------5具體設(shè)計(jì)------------------------------------------------------------------51、數(shù)據(jù)構(gòu)造的設(shè)計(jì)-----------------------------------------5<1>存儲構(gòu)造-------------------------------------------------------5<2>圖的表達(dá)--------------------------------------------------------62、算法的設(shè)計(jì)---------------------------------------------6<1>克魯斯卡爾算法設(shè)計(jì)----------------------------------------------6<2>避免不能構(gòu)成最小生成樹的圖--------------------------------------6<3>模塊構(gòu)造及功效--------------------------------------------------7<4>重要模塊算法描述------------------------------------------------7五、源程序清單-----------------------------------------------------------------9六、測試數(shù)據(jù)及測試成果-----------------------------------------------------91、開始畫面---------------------------------------------------------92、輸入信息---------------------------------------------------------103、數(shù)據(jù)解決---------------------------------------------------------10（1）判斷能否構(gòu)成最小生成樹---------------------------------------10（2）遍歷全部的最小生成樹-----------------------------------------10（3）退出---------------------------------------------------------11七、課程設(shè)計(jì)總結(jié)--------------------------------------------------------------11八、附錄--------------------------------------------------------------------------------11參考書目--------------------------------------------------------------------------15構(gòu)造能夠使n個(gè)都市連接的最小生成樹一、重要問題給定一種地區(qū)的n個(gè)都市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)。二、基本規(guī)定（1）都市間的距離網(wǎng)采用鄰接矩陣表達(dá)，鄰接矩陣的存儲構(gòu)造定義采用課本中給出的定義，若兩個(gè)都市之間不存在道路，則將對應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。規(guī)定在屏幕上顯示得到的最小生成樹中涉及了哪些都市間的道路，并顯示得到的最小生成樹的代價(jià)。（2）表達(dá)都市間距離網(wǎng)的鄰接矩陣（規(guī)定最少6個(gè)都市，10條邊）（3）最小生成樹中涉及的邊及其權(quán)值，并顯示得到的最小生成樹的代價(jià)。三、算法基本思想描述Kruskal算法思想基本描述：假設(shè)連通圖N=（V，{E}），則令最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，圖中每個(gè)頂點(diǎn)自成一種連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。以這類推，直至T中全部頂點(diǎn)都在同一種連通分量上為止。四、具體設(shè)計(jì)1、數(shù)據(jù)構(gòu)造的設(shè)計(jì)<1>存儲構(gòu)造鄰接矩陣存儲辦法（數(shù)組存儲辦法），運(yùn)用兩個(gè)數(shù)組來存儲一種圖，其構(gòu)造原理比較簡樸。對于含有n個(gè)頂點(diǎn)的圖G=(V,E),定義一種含有n個(gè)元素的一維數(shù)組VERTEX[0..n-1]，將圖中頂點(diǎn)的數(shù)據(jù)信息分別存入該數(shù)組的一種數(shù)組元素中。另外，定義一種二維數(shù)組A[0..n-1][0..n-1],該二維數(shù)組普通被稱為鄰接矩陣。若以頂點(diǎn)在VERTEX數(shù)組中的下標(biāo)來代表一種頂點(diǎn)，則鄰接矩陣中元素A[i][j]寄存頂點(diǎn)i到頂點(diǎn)j之間的關(guān)系信息，有1 當(dāng)頂點(diǎn)i與頂點(diǎn)j之間有邊時(shí)A[i][j]=0 當(dāng)頂點(diǎn)i與頂點(diǎn)j之間無邊時(shí)對于網(wǎng)絡(luò)，有當(dāng)頂點(diǎn)i與頂點(diǎn)j之間有邊時(shí)，且邊上的權(quán)值為時(shí)A[i][j]= 當(dāng)頂點(diǎn)i與頂點(diǎn)j之間無邊時(shí)<2>圖的表達(dá)用n表達(dá)都市的個(gè)數(shù)，st表達(dá)起始都市，ed表達(dá)終點(diǎn)都市，dis表達(dá)兩都市間的距離。下面是構(gòu)成該構(gòu)造體的源代碼：typedefstructnode { intst;/*起點(diǎn)*/ inted;/*終點(diǎn)*/ intdis;/*距離*/ }node;nodep[]；/*p[]數(shù)組用來儲存都市和都市間的信息*/2、算法的設(shè)計(jì)<1>克魯斯卡爾算法設(shè)計(jì)a.設(shè)立計(jì)數(shù)器E，初值為0，統(tǒng)計(jì)已選中的邊數(shù)。將全部邊從小到大排序，存于p[]中。b.從p[]中選擇一條權(quán)值最小的邊，檢查其加入到最小生成樹中與否會(huì)構(gòu)成回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計(jì)數(shù)器E累加1。c.從E中刪除此最小邊，轉(zhuǎn)b繼續(xù)執(zhí)行，直到k=n-1,算法結(jié)束d.判斷與否構(gòu)成回路的辦法：

設(shè)立集合S，其中寄存已加入到生成樹中的邊所連接的頂點(diǎn)集合，當(dāng)一條新的邊要加入到生成樹中時(shí)，檢查此邊所連接的兩個(gè)頂點(diǎn)與否都已經(jīng)在S中，若是，則表達(dá)構(gòu)成回路，否則，若有一種頂點(diǎn)不在S中或者兩個(gè)頂點(diǎn)都不在S中，則不夠成回路。<2>避免不能構(gòu)成最小生成樹的圖為避免輸入的圖構(gòu)成的不是連通圖，設(shè)計(jì)了judge()函數(shù)來判斷輸入數(shù)據(jù)構(gòu)成的與否為連通圖，此函數(shù)的重要算法是源于普里姆算法，通過改編，形成了新的函數(shù)。<3>模塊構(gòu)造及功效主程序主程序輸入都市信息退出初始化判斷與否為連通圖求最小生成樹判斷與否構(gòu)成回路將能夠最小生成樹的邊集合打印輸出最小生成樹及代價(jià)打印輸出最小生成樹及代價(jià)intmain() //主程序intmenu() //菜單函數(shù)voidcreate() //輸入都市信息函數(shù)voidjudge() //判斷與否能夠生成最小生成樹函數(shù)voiddisplay()//打印輸出voidset()//初始化pre[],rank[]函數(shù)voidfind（）//判斷與否構(gòu)成回路函數(shù)voidUnion()//將能構(gòu)成最小生成樹的邊添加到一種集合voidKrushal()//克魯斯算法求最小生成樹<4>重要模塊算法描述Krushal算法描述：/*下面三個(gè)函數(shù)作用是檢查當(dāng)一條邊添加進(jìn)去，與否會(huì)產(chǎn)生回路*/voidset(intx)/*初始化*/{ pre[x]=x; rank[x]=0;}intfind(intx)/*找到這個(gè)點(diǎn)的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*將這兩個(gè)添加到一種集合里去*/{ x=find(x); y=find(y); if(rank[x]>=rank[y]) { pre[y]=x; rank[x]++;} elsepre[y]=x; }voidKruskal() { intans=0,i,j,k=0; /*ans用來統(tǒng)計(jì)生成最小樹的權(quán)總值*/ intindex; intcount=0; /*統(tǒng)計(jì)打印邊的條數(shù)*/ for(i=1;i<=n;i++)/*初始化數(shù)組pre[x],rank[x]*/ set(i); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { p[++k].st=i; p[k].ed=j; p[k].dis=a[i][j];/*先把全部都市之間的路段當(dāng)作一種邊*/ } } for(i=1;i<=k;i++) /*把全部的邊按從小到大進(jìn)行排序*/ { index=i; for(j=i+1;j<=k;j++)if(p[j].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { if(find(p[i].st)!=find(p[i].ed))/*如果這兩點(diǎn)連接在一起不構(gòu)成一種回路，則執(zhí)行下面操作*/ { printf("\t第%d條路段為：%d--%d,權(quán)值為%d\n",++count,p[i].st,p[i].ed,p[i].dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來*/ ans+=p[i].dis; /*闡明這條路段要用*/ Union(p[i].st,p[i].ed); } } printf("\t遍歷全部都市得到最小生成樹的代價(jià)為:%d\n\n",ans); }五、源程序清單（詳見附錄）六、測試數(shù)據(jù)及測試成果11以一種6個(gè)都市、10條邊的網(wǎng)絡(luò)圖為例進(jìn)行測試11 161120 11 51119 611221491118網(wǎng)絡(luò)圖GE=鄰接矩陣1、開始畫面2、輸入信息設(shè)立兩頂點(diǎn)之間無邊時(shí)∞權(quán)值為10000003、數(shù)據(jù)解決(1)、判斷能否構(gòu)成最小生成樹（2）、遍歷全部都市生成最小生成數(shù)21 16 2163 11 563 654 1854生成的最小生成樹（3）、退出七、課程設(shè)計(jì)總結(jié)通過最小生成樹的學(xué)習(xí)，我學(xué)會(huì)了樹的多個(gè)存儲構(gòu)造和遍歷辦法，最小生成樹的設(shè)計(jì)能夠應(yīng)用于我們生活中。我們能夠把生活中碰到的實(shí)際問題轉(zhuǎn)化為一種算法問題來進(jìn)行解決。八、附錄源程序：#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructnode/*構(gòu)造一種構(gòu)造體，兩個(gè)都市能夠當(dāng)作起點(diǎn)和終點(diǎn)，之間的道路能夠當(dāng)作一種邊*/{ intst;/*起點(diǎn)*/ inted;/*終點(diǎn)*/ intdis;/*距離*/}node;nodep[1000],temp; /*p統(tǒng)計(jì)都市信息*/intpre[1000],rank[1000];/*用于判斷與否構(gòu)成回路*/intn=0,a[100][100];/*n表達(dá)都市個(gè)數(shù)，a[][]統(tǒng)計(jì)都市間權(quán)值*/intmenu()/*菜單函數(shù)*/{ intm; printf("求最小生成樹\n"); printf("________________________________\n\n"); printf("1輸入都市之間的信息\n"); printf("2判斷與否能構(gòu)成一種最小生成樹\n"); printf("3遍歷全部都市生成最小生成樹\n"); printf("4退出\n"); printf("________________________________\n\n"); printf("請輸入所選功效--4\n"); scanf("%d",&m); returnm;}/*下面三個(gè)函數(shù)作用是檢查當(dāng)一條邊添加進(jìn)去，與否會(huì)產(chǎn)生回路*/voidset(intx)/*初始化*/{ pre[x]=x;}intfind(intx)/*找到這個(gè)點(diǎn)的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*將這兩個(gè)添加到一種集合里去*/{ x=find(x); y=find(y);pre[y]=x;}voidKruskal() { intans=0,i,j,k=0; /*ans用來統(tǒng)計(jì)生成最小樹的權(quán)總值*/ intindex; intcount=0; /*統(tǒng)計(jì)打印邊的條數(shù)*/ for(i=1;i<=n;i++)/*初始化數(shù)組pre[x],rank[x]*/ set(i); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { p[++k].st=i; p[k].ed=j; p[k].dis=a[i][j];/*先把全部都市之間的路段當(dāng)作一種邊*/ } } for(i=1;i<=k;i++) /*把全部的邊按從小到大進(jìn)行排序*/ { index=i; for(j=i+1;j<=k;j++)if(p[j].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { if(find(p[i].st)!=find(p[i].ed))/*如果這兩點(diǎn)連接在一起不構(gòu)成一種回路，則執(zhí)行下面操作*/ { printf("\t第%d條路段為：%d--%d,權(quán)值為%d\n",++count,p[i].st,p[i].ed,p[i].dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來*/ ans+=p[i].dis; /*闡明這條路段要用*/ Union(p[i].st,p[i].ed); } } printf("\t遍歷全部都市得到最小生成樹的代價(jià)為:%d\n\n",ans); }voidcreate() /*輸入都市信息*/ { inti,j; if(n!=0) { charstr[100]; printf("與否要擬定輸入新的都市之間的信息?(y/n)?\n"); scanf("%s",str); if(strcmp(str,"n")==0) return; } printf("請輸入都市的個(gè)數(shù):\n"); scanf("%d",&n); printf("輸入%d個(gè)都市的鄰接矩陣:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%d",&a[i][j]); } }voiddisplay() /*顯示生成的最小生成樹*/ { if(n==0) { printf("這里沒有都市之間的信息\n"); return; } printf("遍歷全部都市得到最小生成樹為：\n\n\n"); Kruskal(); }voidjudge()/*判斷與否能夠生成最小生成樹*/ { intclose[100],low[100],i,j,ans=0;/*close[j]表達(dá)離j近來的頂點(diǎn)，low[j]表達(dá)離j最短的距離*/ intuse[100]; use[1]=1; for(i=2;i<=n;i++) {low[i]=a[1][i];/*初始化*/close[i]=1;use[i]=0;