《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》建立通信網(wǎng)絡(luò)在n個城市建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。設(shè)計算法，求出如果以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)絡(luò)。要求如下：至少包含10個城市；城市數(shù)n由鍵盤錄入；城市坐標(biāo)由隨機函數(shù)產(chǎn)生小于100的整數(shù)；輸出生成樹中各條邊以及它們的權(quán)值；1．課程設(shè)計目的通過做實驗報告，發(fā)現(xiàn)問題，解決問題來熟練掌握圖的定義、儲存結(jié)構(gòu)和鄰接矩陣表示方法等等，再用kruskal算法和prim算法來實現(xiàn)求最小生成樹的權(quán)值，再把它運用到現(xiàn)實生活當(dāng)中去.2．需求分析2.1問題描述：要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟建設(shè)這個通信網(wǎng)，是一個網(wǎng)的最小生成樹。2.2設(shè)計要求：可以用連通網(wǎng)來表示n個城市間可能設(shè)置的通信網(wǎng)絡(luò)，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的路線，邊的權(quán)值表示相應(yīng)的費用。對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)?，F(xiàn)在，我們要選擇這樣一棵生成樹，它使總的費用最少，這棵樹就是最小生成樹。一棵生成樹的費用就是樹上各邊的費用之和。本程序的目的是要建設(shè)一個最經(jīng)濟的通信網(wǎng)，根據(jù)用戶輸入的網(wǎng)，輸出相應(yīng)的最小生成樹。在這里城市以及兩城市之間的費用都用整型數(shù)來代替。利用克魯斯卡爾算法和普利姆算法實現(xiàn)。①克魯斯卡爾算法：要求設(shè)計程序輸入如下：(1)圖的頂點可以輸入數(shù)字或字母，連著輸入，之間不需要空格。（2）必須按規(guī)格輸入相應(yīng)的鄰接矩陣，否則會出錯。程序所能達到的功能：直接實現(xiàn)最小生成樹權(quán)值的計算。②普利姆算法:要求設(shè)計程序輸入如下：(1)數(shù)據(jù)城市間的距離網(wǎng)采用鄰接矩陣表示。（2）若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。（3）輸入圖的頂點可以只能是數(shù)字，不能是字母，不然會出錯。程序所能達到的功能：屏幕顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的權(quán)值之和。3．概要設(shè)計3.1概要問題分析：（1）最小生成樹的定義：對于一個帶權(quán)（假定每條邊上的權(quán)值均大于零的實數(shù)）連通無向圖G中的不同生成樹，其每棵樹的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹中的具有邊上的權(quán)值之和最小的樹成為圖的最小生成樹。（2）最小生成樹的典型用途：欲在n個城市間建立通信網(wǎng).n個城市可能有n(n-1)/2條線路，但鋪n-1條線路即可連通；因為每條線路都會有對應(yīng)的經(jīng)濟成本，那么，如何選擇n–1條線路，使總費用最少？（3）構(gòu)造數(shù)學(xué)模型：頂點———表示城市，有n個；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟代價；連通網(wǎng)——表示n個城市間通信網(wǎng)。（4）最小生成樹的操作：Prim算法：假設(shè)G=(V,E)是連通圖，T=(U,TE)為欲構(gòu)造的最小生成樹，初始化U={u0}，TE為空，重復(fù)以下操作：在所有u∈U,v∈V-U的邊(u,v)∈E中，選擇一條權(quán)最小的邊(u,v)并入TE，同時將v并入U，直到U=V為止，此時T=(U,TE)是G的一棵最小生成樹。kruskal算法：分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費遞增的順序來考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。代碼采用鄰接矩陣表示圖，采用邊集表示法。3.2概要設(shè)計①克魯斯卡爾算法：1.①定義一個邊集結(jié)構(gòu)，用來存儲圖的所有邊信息。②構(gòu)造鄰接矩陣法圖的生成函。③MSTEdge數(shù)組，用來存儲已確定的MST的邊的編號，共VertexNum-1條邊。④用Kruskal算法生成MST。2.本程序包含6個函數(shù)：(1)主函數(shù)main()(2)鄰接矩陣法圖的生成函數(shù)voidCreateGraph(Graph*g)(3)打印圖的結(jié)點標(biāo)識符和鄰接矩陣voidPrintGraph(Graphg)(4)intCalVerNum(Graphg)//圖的頂點數(shù)(5)intCalEdgNum(Graphg)//獲取圖的邊數(shù)(6)voidKruskal(Graphg)//Kruskal算法生成MST②普利姆算法:1.本程序包含6個函數(shù)：(1)主函數(shù)main()(2)intLocate(MGraph&g,intV)//求頂點位置函數(shù)(3)MGraphCreateMap(MGraph&g)//創(chuàng)建圖(4)intMin(MGraph&g,Nodeclosest[])//closest[]中權(quán)值最小的邊(5)voidprim(MGraph&g,intu)//從頂點u出發(fā)構(gòu)造連通圖g的最小生成樹，并輸出生成樹的每條(6)voiddisplay(MGraph&g)//輸出鄰接矩陣算法2.Prim算法流程設(shè)計:如圖七個城市之間共有11條路，運用Prim算法：選定第一個點⑥，從它closest的邊中選擇最短邊⑥⑦,權(quán)值為2；⑥⑤，權(quán)值為3；⑥③，權(quán)值為5；③①，權(quán)值為5；⑤④，權(quán)值為6；④②，權(quán)值為4；所得最小生成樹的權(quán)值為2+3+5+5+6+4=25.4詳細設(shè)計4.1克魯斯卡爾算法：typedefstructGraph{ //定義圖的鄰接矩陣表示法結(jié)構(gòu)VertexTypever[MaxSize+1];intedg[MaxSize][MaxSize];}Graph;2.typedefstructgEdge{ //定義一個邊集結(jié)構(gòu)，用來存儲圖的所有邊信息intbegin;intend;intweight;}gEdge;(1)主函數(shù)intmain(){Graphg;CreateGraph(&g);PrintGraph(g);Kruskal(g);return0;}(2)intCalVerNum(Graphg)//求圖的頂點數(shù){returnstrlen(g.ver);}intCalEdgNum(Graphg)//獲取圖的邊數(shù){Graphp=g;intcount=0;intVertexNum=CalVerNum(p);for(inti=0;i<VertexNum;i++)for(intj=i;j<VertexNum;j++) //鄰接矩陣對稱，計算上三角元素和就可以了if(0!=p.edg[i][j])count++;returncount;}(3)鄰接矩陣法圖的生成函數(shù)：voidCreateGraph(Graph*g){ inti=0; intj=0; intVertexNum; VertexTypeVer; printf("請輸入圖的頂點:\n"); while('\n'!=(Ver=getchar())){g->ver[i++]=Ver; } g->ver[i]='\0'; VertexNum=strlen(g->ver); printf("請輸入相應(yīng)的的鄰接矩陣:\n"); for(i=0;i<VertexNum;i++) for(j=0;j<VertexNum;j++) scanf("%d",&g->edg[i][j]);}(4)打印圖的結(jié)點標(biāo)識符和鄰接矩陣voidPrintGraph(Graphg){ inti,j; intVertexNum=strlen(g.ver); printf("圖的頂點為:\n"); for(i=0;i<VertexNum;i++)printf("%c",g.ver[i]); printf("\n"); printf("圖的鄰接矩陣為:\n"); for(i=0;i<VertexNum;i++){for(j=0;j<VertexNum;j++) printf("%d",g.edg[i][j]); printf("\n"); }}(5)Kruskal算法生成MSTvoidKruskal(Graphg){ intVertexNum=CalVerNum(g); intEdgNum=CalEdgNum(g); gEdge*p=CreateEdges(g); int*index=(int*)malloc(sizeof(int)*VertexNum); //index數(shù)組，其元素為連通分量的編號，index[i]=index[j]表示編號為i和j的頂點在同一個連通分量中，反之則不在同一個連通分量 int*MSTEdge=(int*)malloc(sizeof(int)*VertexNum-1);//MSTEdge數(shù)組，用來存儲已確定的MST的邊的編號，共VertexNum-1條邊 intk=0; intWeightSum=0; intIndexBegin,IndexEnd; for(inti=0;i<VertexNum;i++)//初始化所有index=-1 index[i]=-1; for(i=0;i<VertexNum-1;i++){ for(intj=0;j<EdgNum;j++){ if(!(index[p[j].begin]>=0&&index[p[j].end]>=0&&index[p[j].begin]==index[p[j].end])){//找到當(dāng)前還沒加入到同一個連通分量且權(quán)值最下的邊 MSTEdge[i]=j;//將其加入到MST中去 if((-1==index[p[j].begin])&&(-1==index[p[j].end]))//該邊的兩個頂點都沒加入過任何一個連通分量 index[p[j].begin]=index[p[j].end]=i; elseif((-1==index[p[j].begin])&&(index[p[j].end]>=0)){ //該邊的尾end已在一個連通分量，頭begin未加入過任何連通分量 index[p[j].begin]=i; IndexEnd=index[p[j].end]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexEnd) index[n]=i;}elseif((-1==index[p[j].end])&&(index[p[j].begin]>=0)){ //該邊的頭begin已在一個連通分量，尾end未加入過任何連通分量 index[p[j].end]=i; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++)if(index[n]==IndexBegin)index[n]=i;}else{IndexEnd=index[p[j].end]; IndexBegin=index[p[j].begin];for(intn=0;n<VertexNum;n++)//該邊的兩個頂點都已經(jīng)存在于兩個不同的連通分中if(index[n]==IndexBegin||index[n]==IndexEnd) index[n]=i;//將該連通分量編號全部修改為相同的值} break; } } } printf("MST的邊為:\n");//輸出MST的邊 for(i=0;i<VertexNum-1;i++){ printf("%c--%c\n",g.ver[p[MSTEdge[i]].begin],g.ver[p[MSTEdge[i]].end]); WeightSum+=p[MSTEdge[i]].weight; } printf("MST的權(quán)值為:%d\n",WeightSum); //輸出MST的權(quán)值}注：具體源代碼見附錄4.2普利姆算法:4.2.1主函數(shù)：voidmain(){intst;MGraphg;cout<<"\n*********************n個城市的最小生成樹*****************"<<endl;CreateMap(g); {cout<<"\n該圖所對應(yīng)的鄰接矩陣如下:"<<endl;display(g);cout<<endl<<"請輸入起點城市編號:";cin>>st;while(1) {if(st==0)break;elseif(st>g.n)cout<<"輸入起點城市編號有錯，請重新輸入!"<<endl;else {prim(g,st);cout<<"\n*************************************************"<<endl; }cout<<endl<<"請繼續(xù)輸入起點城市,否則輸入0退出!"<<endl;cin>>st; } }}4.2.2創(chuàng)建圖MGraphCreateMap(MGraph&g){inti,j,k,v1,v2,vex,m=1;cout<<"請輸入城市的個數(shù)：";cin>>g.n;if(g.n<=1){cout<<"最小生成樹不存在!"<<endl;returng;}else{cout<<"請輸入城市的邊數(shù)：";cin>>g.e;for(i=0;i<g.n;i++)//初始化鄰接矩陣for(j=0;j<g.n;j++)if(i==j)g.city[i][j].weight=0;elseg.city[i][j].weight=INF;cout<<"請輸入城市的頂點編號：";//輸入圖中的頂點編號for(i=0;i<g.n;i++)cin>>g.vexs[i];cout<<"輸入每條邊所對應(yīng)的兩個頂點及權(quán)值<格式：起點城市終點城市權(quán)值>!"<<endl;for(k=0;k<g.e;k++){cout<<"請輸入第"<<m++<<"條邊：";cin>>v1>>v2>>vex;//輸入一條邊的兩個頂點及權(quán)值i=Locate(g,v1);j=Locate(g,v2);g.city[i][j].weight=vex;g.city[j][i].weight=vex;}return(g);}}4.2.3輸出鄰接矩陣算法voiddisplay(MGraph&g){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.city[i][j].weight==INF)cout<<"\t"<<"∞";elsecout<<"\t"<<g.city[i][j].weight;cout<<endl;}}4.2.4構(gòu)造連通圖g的最小生成樹voidprim(MGraph&g,intu)//從頂點u出發(fā),構(gòu)造連通圖g的最小生成樹，并輸出生成樹的每條邊{MGraphp;inti,j,k,k0,u0,v0,s=0,n=0;k=Locate(g,u);//k為頂點u的位置p.vexs[n++]=u;closest[k].lowcost=0;//初始化U={u}for(i=0;i<g.n;i++)if(i!=k)//初始化closest[i]{closest[i].vex=u;closest[i].lowcost=g.city[k][i].weight;}for(j=1;j<=g.n-1;j++)//選擇其余的n-1條邊(n=g.n){k0=Min(g,closest);//closest[k0]中存有當(dāng)前最小邊(u0,v0)的信息u0=closest[k0].vex;//u0∈Uv0=g.vexs[k0];//v0∈V-Up.vexs[n++]=v0;s+=closest[k0].lowcost;//求最小生成樹的權(quán)值之和cout<<"從編號為"<<u0<<"的城市到編號為"<<v0<<"的城市"<<"的權(quán)值為"<<closest[k0].lowcost<<endl;//輸出最小生成樹的路徑closest[k0].lowcost=0;//將頂點v0納入U集合for(i=0;i<g.n;i++)//在頂點v0并入U之后,重新選擇最小邊if(g.city[k0][i].weight<closest[i].lowcost){closest[i].lowcost=g.city[k0][i].weight;closest[i].vex=v0;}}cout<<"\n最小生成樹的權(quán)值之和為："<<s<<endl;}注：具體源代碼見附錄5調(diào)試分析5.1克魯斯卡爾算法測試當(dāng)鄰接矩陣輸入錯誤是會有如圖所示的提示：注意：輸入的鄰接矩陣必須按規(guī)范來，不能多輸入一個頂點或少一個頂點。5.2普利姆算法測試手動輸入城市頂點個數(shù)和鄰接矩陣：

5.3測試結(jié)果繼續(xù)輸入，換個起點城市編號最小生成樹的權(quán)值之和也一樣6．課程設(shè)計總結(jié)通過做這次實驗報告，讓我對數(shù)據(jù)結(jié)構(gòu)以及C語言的應(yīng)用有了更深的掌握了解，更是讓我認識到了數(shù)據(jù)結(jié)構(gòu)算法的重要性！??！算法雖然很復(fù)雜，讓人很難理解，但只要耐下心來一步一步去弄懂每個語句，再運用到實踐當(dāng)中去實現(xiàn)一些功能還是容易熟練掌握的。幸虧自己有一定的C語言基礎(chǔ)和離散數(shù)學(xué)基礎(chǔ)，不然去理解最小生成樹和鄰接矩陣的概念還是挺費勁的。

7．附錄（源代碼）①克魯斯卡爾算法：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMaxSize20typedefcharVertexType;typedefstructGraph{ //定義圖的鄰接矩陣表示法結(jié)構(gòu) VertexTypever[MaxSize+1]; intedg[MaxSize][MaxSize];}Graph;typedefstructgEdge{ //定義一個邊集結(jié)構(gòu)，用來存儲圖的所有邊信息 intbegin; intend; intweight;}gEdge;voidCreateGraph(Graph*g) //鄰接矩陣法圖的生成函數(shù){ inti=0; intj=0; intVertexNum; VertexTypeVer; printf("請輸入圖的頂點:\n"); while('\n'!=(Ver=getchar())){ g->ver[i++]=Ver; } g->ver[i]='\0'; VertexNum=strlen(g->ver); printf("請輸入相應(yīng)的的鄰接矩陣:\n"); for(i=0;i<VertexNum;i++) for(j=0;j<VertexNum;j++) scanf("%d",&g->edg[i][j]);}voidPrintGraph(Graphg) //打印圖的結(jié)點標(biāo)識符和鄰接矩陣{ inti,j; intVertexNum=strlen(g.ver); printf("圖的頂點為:\n"); for(i=0;i<VertexNum;i++) printf("%c",g.ver[i]); printf("\n"); printf("圖的鄰接矩陣為:\n"); for(i=0;i<VertexNum;i++){ for(j=0;j<VertexNum;j++) printf("%d",g.edg[i][j]); printf("\n"); }}intCalVerNum(Graphg) //求圖的頂點數(shù){ returnstrlen(g.ver);}intCalEdgNum(Graphg) //獲取圖的邊數(shù){ Graphp=g; intcount=0; intVertexNum=CalVerNum(p); for(inti=0;i<VertexNum;i++) for(intj=i;j<VertexNum;j++) //鄰接矩陣對稱，計算上三角元素和即可 if(0!=p.edg[i][j]) count++; returncount;}gEdge*CreateEdges(Graphg) //生成圖的排序過的邊集數(shù)組{ inti,j; intk=0; intEdgNum=CalEdgNum(g); intVertexNum=CalVerNum(g); gEdgetemp; gEdge*p=(gEdge*)malloc(sizeof(gEdge)*EdgNum); for(i=0;i<VertexNum;i++) //邊集數(shù)組初始化,同樣只考慮上三角矩陣 for(j=i;j<VertexNum;j++) if(0!=g.edg[i][j]){ p[k].begin=i; p[k].end=j; p[k].weight=g.edg[i][j]; k++; } for(i=0;i<EdgNum-1;i++) //對邊集數(shù)組進行選擇排序 for(j=i+1;j<EdgNum;j++) if(p[i].weight>p[j].weight){ temp=p[i]; p[i]=p[j]; p[j]=temp; } returnp;}//Kruskal算法生成MSTvoidKruskal(Graphg){ intVertexNum=CalVerNum(g); intEdgNum=CalEdgNum(g); gEdge*p=CreateEdges(g); int*index=(int*)malloc(sizeof(int)*VertexNum); //index數(shù)組，其元素為連通分量的編號，index[i]=index[j]表示編號為i和j的頂點在同一個連通分量中，反之則不在同一個連通分量 int*MSTEdge=(int*)malloc(sizeof(int)*VertexNum-1); //MSTEdge數(shù)組，用來存儲已確定的MST的邊的編號，共VertexNum-1條邊 intk=0; intWeightSum=0; intIndexBegin,IndexEnd; for(inti=0;i<VertexNum;i++) //初始化所有index=-1 index[i]=-1; for(i=0;i<VertexNum-1;i++){ for(intj=0;j<EdgNum;j++){ if(!(index[p[j].begin]>=0&&index[p[j].end]>=0&&index[p[j].begin]==index[p[j].end])){//找到當(dāng)前還沒加入到同一個連通分量且權(quán)值最下的邊 MSTEdge[i]=j; //將其加入到MST中去 if((-1==index[p[j].begin])&&(-1==index[p[j].end])) //該邊的兩個頂點都沒加入過任何一個連通分量 index[p[j].begin]=index[p[j].end]=i; elseif((-1==index[p[j].begin])&&(index[p[j].end]>=0)){ //該邊的尾end已在一個連通分量，頭begin未加入過任何連通分量 index[p[j].begin]=i; IndexEnd=index[p[j].end]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexEnd) index[n]=i; } elseif((-1==index[p[j].end])&&(index[p[j].begin]>=0)){ //該邊的頭begin已在一個連通分量，尾end未加入過任何連通分量 index[p[j].end]=i; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexBegin) index[n]=i; } else{ IndexEnd=index[p[j].end]; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++) //該邊的兩個頂點都已經(jīng)存在于兩個不同的連通分量中 if(index[n]==IndexBegin||index[n]==IndexEnd) index[n]=i; //將該連通分量編號全部修改為相同的值 } break; } } } printf("MST的邊為:\n"); //輸出MST的邊 for(i=0;i<VertexNum-1;i++){ printf("%c--%c\n",g.ver[p[MSTEdge[i]].begin],g.ver[p[MSTEdge[i]].end]); WeightSum+=p[MSTEdge[i]].weight; } printf("MST的權(quán)值為:%d\n",WeightSum); //輸出MST的權(quán)值}intmain(){ Graphg; CreateGraph(&g); PrintGraph(g); Kruskal(g); return0;}②普利姆算法:#include<iostream.h>#include<stdio.h>#include<string.h>#include<malloc.h>constintMAXV=30;//最多頂點個數(shù)constintINF=32768;//表示極大值，即∞structNode{intweight;intvex;//存放頂點編號intlowcost;//存放頂點權(quán)值};structMGraph{intvexs[MAXV],n,e;//vexs表示頂點向量;n,e分別表示圖的頂點數(shù)和邊數(shù)Nodecity[MAXV][MAXV];//鄰接矩陣};Nodeclosest[MAXV];//求最小生成樹時的輔助數(shù)組intLocate(MGraph&g,intV)//求頂點位置函數(shù){intj=-1,k;for(k=0;k<g.n;k++)if(g.vexs[k]==V) {j=k;break; }returnj;}MGraphCreateMap(MGraph&g)//創(chuàng)建圖{inti,j,k,v1,v2,vex,m=1;cout<<"請輸入城市的個數(shù)：";cin>>g.n;if(g.n<=1) {cout<<"最小生成樹不存在!"<<endl;returng; }else {cout<<"請輸入城市的邊數(shù)：";cin>>g.e;for(i=0;i<g.n;i++)//初始化鄰接矩陣for(j=0;j<g.n;j++)if(i==j)g.city[i][j].weight=0;elseg.city[i][j].weight=INF;cout<<"請輸入城市的頂點編號：";//輸入圖中的頂點編號for(i=0;i<g.n;i++)cin>>g.vexs[i];cout<<"輸入每條邊所對應(yīng)的兩個頂點及權(quán)值<格式：起點城市終點城市權(quán)值>!"<<endl;for(k=0;k<g.e;k++) {cout<<"請輸入第"<<m++<<"條邊：";cin>>v1>>v2>>vex;//輸入一條邊的兩個頂點及權(quán)值i=Locate(g,v1);j=Locate(g,v2);g.city[i][j].weight=vex;g.city[j][i].weight=vex; }return(g); }}intMin(MGraph&g,Nodeclosest[])//closest[]中權(quán)值最小的邊{inti,min,j;min=INF;for(i=0;i<g.n;i++)if(closest[i].lowcost<min&&closest[i].lowcost!=0) {min=closest[i].lowcost;j=i; }returnj;//返回權(quán)值最小的邊在輔助數(shù)組中的位置}voidprim(MGraph&g,intu)//從頂點u出發(fā),按普里姆算法構(gòu)造連通圖g的最小生成樹，并輸出生成樹的每條邊{MGraphp;inti,j,k,k0,u0,v0,s=0,n=0;k=Locate(g,u);//k為頂點u的位置p.vexs[n++]=u;closest[k].lowcost=0;//初始化U={u}for(i=0;i<g.n;i++)if(i!=k)//初始化closest[i] {closest[i].vex=u;closest[i].lowcost=g.city[k][i].weight;