圖的深度和廣度遍歷

XXX計(jì)算機(jī)軟件基礎(chǔ)課程設(shè)計(jì)題目：圖的深度和廣度遍歷學(xué)院：信息與通信工程學(xué)院專(zhuān)業(yè)：通信工程專(zhuān)業(yè)學(xué)生姓名：班級(jí)/學(xué)號(hào)指導(dǎo)老師：起止時(shí)間：1XXX本小組的任務(wù)是圖的深度遍歷和廣度遍歷，根據(jù)分配，我做的是圖的最小生成樹(shù)。由于最小生成樹(shù)軟件基礎(chǔ)的書(shū)上沒(méi)有具體的程序過(guò)程，故而，在課余時(shí)間閱讀了一些有關(guān)算法設(shè)計(jì)與分析的圖書(shū)，在此基礎(chǔ)上，借鑒了用prim和kruskal算法求解最小生成樹(shù)的方法，也以此檢驗(yàn)自己一學(xué)期所學(xué)成果，加深對(duì)算法設(shè)計(jì)與分析這門(mén)課程的理解，由于所學(xué)知識(shí)有限，難免有些繁瑣和不完善之處，下面簡(jiǎn)單介紹此程序的設(shè)計(jì)原理，方法，內(nèi)容及設(shè)計(jì)的結(jié)果。本程序主要利用數(shù)組，for語(yǔ)句的循環(huán)，if語(yǔ)句的嵌套，運(yùn)用以上所學(xué)知識(shí)編寫(xiě)出的prim和kruskal便可分別輸出此圖的prim和kruskal算法最小生成樹(shù)的邊的起始位置，終止位置以及權(quán)值。2XXX目錄1123123XXX二：相關(guān)介紹：1、DLL函數(shù)（1）原理：動(dòng)態(tài)鏈接庫(kù)英文為DLL，是DynamicLinkLibrary的縮寫(xiě)形式，DLL是一個(gè)包含可由多個(gè)程序同時(shí)使用的代碼和數(shù)據(jù)的庫(kù)，DLL不是可執(zhí)行文件。動(dòng)態(tài)鏈接庫(kù)中定義有兩種函數(shù)：導(dǎo)出函數(shù)(exportfunction)和內(nèi)部函數(shù)(internalfunction)。導(dǎo)出函數(shù)可以被其它模塊調(diào)用，內(nèi)部函數(shù)在定義它們的DLL程序內(nèi)部使用。動(dòng)態(tài)鏈接提供了一種方法，使進(jìn)程可以調(diào)用不屬于其可執(zhí)行代碼的函數(shù)。函數(shù)的可執(zhí)行代碼位于一個(gè)DLL中，該DLL包含一個(gè)或多個(gè)已被編譯、鏈接并與使用它們的進(jìn)程分開(kāi)存儲(chǔ)的函數(shù)。DLL還有助于共享數(shù)據(jù)和資源。多個(gè)應(yīng)用程序可同時(shí)訪問(wèn)內(nèi)存中單個(gè)DLL副本的內(nèi)容。DLL是一個(gè)包含可由多個(gè)程序同時(shí)使用的代碼和數(shù)據(jù)的庫(kù)。2、最小生成樹(shù)方法之Kruskal算法（1Kruskal算法是一種按照連通網(wǎng)中邊的權(quán)值的遞增順序構(gòu)造最小生成樹(shù)的算法。將無(wú)向圖的所有邊按權(quán)值遞增順序排列，依次選定權(quán)值數(shù)較小的邊，但要求后面選取的邊不能與前面選區(qū)的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，n個(gè)頂點(diǎn)的圖中，選取n-1條邊即可。注意kruskal算法分n步，其中n是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來(lái)考慮這n條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。3、最小生成樹(shù)方法之Prim算法（1）原理：力求從源點(diǎn)到下一個(gè)點(diǎn)的距離最短，以此來(lái)構(gòu)建臨接矩陣，所以此算法的核心思想是求得源點(diǎn)到下一個(gè)點(diǎn)的最短距離。從一個(gè)點(diǎn)出發(fā)，列出這個(gè)點(diǎn)所有鄰接的邊，選擇最小的邊，將所連頂點(diǎn)到樹(shù)中，再到剩余的點(diǎn)中找與這兩點(diǎn)（其中之一）距離最小的點(diǎn)加入之中。根據(jù)這一指導(dǎo)思想，我把主程序?qū)懙暮?jiǎn)單些，分別調(diào)用不同的子函數(shù)來(lái)實(shí)現(xiàn)最小生成樹(shù)的prim算法。由于要計(jì)算權(quán)值所4XXXmap[1][2]=map[2][1]=4。先選取一個(gè)點(diǎn)作起始點(diǎn)，然后選擇它鄰近的權(quán)值最小的點(diǎn)（如果有多個(gè)與其相連的點(diǎn)。如此類(lèi)推...三：詳細(xì)設(shè)計(jì)說(shuō)明1、編寫(xiě)DLL函數(shù)（1）函數(shù)：#include"stdafx.h"#include"stdlib.h"extern"C"_declspec(dllimport)intsushu(inti);extern"C"_declspec(dllexport)intsushu(intn){inti;for(i=2;i<n;i++)if(n%i)return1;elsereturn0;}intmain(intargc,char*argv[]){inti=1,m;printf("輸入的數(shù)字為:");scanf("%d",&m);printf("素?cái)?shù)有：\n");while(i+1<=m){i++;if(sushu(i))printf("%d\t",i);}5XXXsystem("pause");return0;}2、最小生成樹(shù)算法（1）鄰接表的存儲(chǔ)和建立存儲(chǔ)：對(duì)于此課題來(lái)說(shuō)，先要建立的就是鄰接表，鄰接表建立出來(lái)才能進(jìn)行圖的遍歷和搜索最小生成樹(shù)。無(wú)向圖的鄰接表對(duì)于圖G中的每個(gè)頂點(diǎn)vi，該方法把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。單鏈表中的每個(gè)結(jié)點(diǎn)至少包含兩個(gè)域，一個(gè)為鄰接點(diǎn)域（adjvex它指示與頂點(diǎn)vi鄰接的頂點(diǎn)在圖中的位序，另一個(gè)為鏈域（next點(diǎn)vi鄰接的下一個(gè)結(jié)點(diǎn)。為了便于隨機(jī)訪問(wèn)任一頂點(diǎn)的鄰接表，可將所有頭結(jié)點(diǎn)順序存儲(chǔ)在一個(gè)向量中就構(gòu)成了圖的鄰接表存儲(chǔ)。最后將圖的頂點(diǎn)數(shù)及邊數(shù)等信息與鄰接表放在一起來(lái)描述圖的存儲(chǔ)結(jié)構(gòu)。建立：voidinitgraph(algraph&T)//圖的初始化函數(shù){printf("輸入圖結(jié)點(diǎn)的個(gè)數(shù)和弧的個(gè)數(shù):");scanf("%d%d",&T.vexnum,&T.arcnum);getchar();T.vertices=(vnode*)malloc(T.vexnum*sizeof(vnode));//開(kāi)辟vnode類(lèi)型的空間，將首地址給T.verticesprintf("輸入這%d個(gè)結(jié)點(diǎn)的標(biāo)識(shí):",T.vexnum);for(inti=0;i<T.vexnum;i++)//輸入圖結(jié)點(diǎn)標(biāo)識(shí){scanf("%c",&(T.vertices+i)->data);while(''==(T.vertices+i)->data)//屏蔽空格鍵{scanf("%c",&(T.vertices+i)->data);6XXX}(T.vertices+i)->firstarc=NULL;//將指針置為空}}intlocalvex(algraph&T,charch)//獲取圖中對(duì)應(yīng)的圖標(biāo)識(shí)對(duì)應(yīng)的下標(biāo){for(inti=0;i<T.vexnum;i++){if(ch==(T.vertices+i)->data)//找到后就退出{break;}}returni;//返回找到的下標(biāo)}（2）Kruskal算法：步驟：（1）定義網(wǎng)中的頂點(diǎn)數(shù)，網(wǎng)的邊數(shù)，這里將網(wǎng)的頂點(diǎn)數(shù)定為6個(gè)，網(wǎng)的邊數(shù)定為10個(gè)。（2）定義一個(gè)名為edgeset2的類(lèi)，其數(shù)據(jù)成員fromvex,endvex,weight,分別為一條邊的起點(diǎn)，終點(diǎn)和權(quán)值。（3）定義一個(gè)名為tree2的類(lèi)，定義了一個(gè)最小生成樹(shù)邊集的數(shù)組，用edgesetge2[e+1]存放網(wǎng)中所有的邊，定義一個(gè)s2[n+1][n+1]，s為一個(gè)集合，一行元素s[i][0]~s[i][n]表示一個(gè)集合，若s[i][t]=1。則表示頂點(diǎn)t屬于該集合，否則不屬于該集合，再定義一個(gè)普里姆算法的成員函數(shù)kruskal(tree2&t2)。（（4）對(duì)kruskal(tree2&t2)函數(shù)進(jìn)行類(lèi)外定義,定義k并設(shè)初值為1用來(lái)統(tǒng)計(jì)生成樹(shù)的邊數(shù)，定義d并設(shè)初值為1用來(lái)表示待掃描邊的下標(biāo)位置，定義兩個(gè)7XXX變量m1,m2用來(lái)記錄一條邊的兩個(gè)頂點(diǎn)所在集合的序號(hào)，如果t2.ge2[d].fromvex==j且t2.s2[i][j]==1，則令m1=i，若t2.ge2[d].endvex==j且t2.s2[i][j]==1則令m2=i，最后判斷m1是否等于m2，若不等于則令t2.c2[k]=t2.ge2[d]k自加，求出一條邊后，合并兩個(gè)集合，另一個(gè)集合設(shè)置為空。（5）最后利用for循環(huán)鍵入每條邊的起始點(diǎn)，終結(jié)點(diǎn)及邊上的權(quán)值，要求輸入的網(wǎng)中的邊上的權(quán)值必須為從大到小排列，調(diào)用kruskal（t）循環(huán)輸出一條邊的起始點(diǎn)，終結(jié)點(diǎn)及邊上的權(quán)值。函數(shù)：#include<iostream.h>constintn=6;//網(wǎng)中頂點(diǎn)數(shù)constinte=10;//網(wǎng)中邊數(shù)classedgeset//定義一條生成樹(shù)的邊的類(lèi){public:intfromvex;//邊的起點(diǎn)intendvex;//邊的終點(diǎn)intweight;//邊的權(quán)值};classedgeset2{public:intfromvex;intendvex;intweight;};classtree2//定義生成樹(shù){public:edgesetc2[n];//存放生成樹(shù)的邊edgesetge2[e+1];//存放網(wǎng)中所有邊8XXXints2[n+1][n+1];//s為一個(gè)集合，一行元素s[i][0]~s[i][n]表示一個(gè)集合//若s[i][t]=1。則表示頂點(diǎn)t屬于該集合，否則不屬于voidkruska(tree2&t2);};voidtree2::kruska(tree2&t2){inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)t2.s2[i][j]=1;elset2.s2[i][j]=0;intk=1;//統(tǒng)計(jì)生成樹(shù)的邊數(shù)intd=1;//表示待掃描邊的下標(biāo)位置intm1,m2;//記錄一條邊的兩個(gè)頂點(diǎn)所在集合的序號(hào)while(k<n){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if((t2.ge2[d].fromvex==j)&&(t2.s2[i][j]==1))m1=i;if((t2.ge2[d].endvex==j)&&(t2.s2[i][j]==1))m2=i;}if(m1!=m2){t2.c2[k]=t2.ge2[d];k++;for(j=1;j<=n;j++){t2.s2[m1][j]=t2.s2[m1][j]||t2.s2[m2][j];//求出一條邊后，合并兩個(gè)集合9XXXt2.s2[m2][j]=0;//另一個(gè)集合設(shè)置為空}}d++;}}（3）prim算法步驟：（1）定義網(wǎng)中的頂點(diǎn)數(shù)，網(wǎng)的邊數(shù)，這里將網(wǎng)的頂點(diǎn)數(shù)定為6個(gè)，網(wǎng)的邊數(shù)定為10個(gè)。(2)定義一個(gè)名為edgeset類(lèi)，其數(shù)據(jù)成員fromvex,endvex,weight,分別為一條邊的起點(diǎn)，終點(diǎn)和權(quán)值。（3）定義一個(gè)名為tree的類(lèi)，定義了一個(gè)最小生成樹(shù)邊集的數(shù)組，用數(shù)組記錄具有最小代價(jià)的邊，找到后，將該邊作為最小生成樹(shù)的樹(shù)邊保存起來(lái)，再定義一個(gè)普里姆算法的成員函數(shù)prim(tree&t)。（4）對(duì)prim(tree&t)函數(shù)進(jìn)行類(lèi)外定義，分別將頂點(diǎn)數(shù)定義為k,邊為m,權(quán)值為w,定義一個(gè)變量min，使其等于32767，即無(wú)窮大，利用for循環(huán)從頂點(diǎn)1出發(fā)求最小生成的數(shù)邊，即設(shè)t.ct[i].fromvex=1。令終止點(diǎn)t.ct[i].endvex=i+1,令t.ct[i].weight=t.s[1][i+1],再利用第二個(gè)for循環(huán)找到權(quán)值最小的樹(shù)邊，從頂點(diǎn)為2開(kāi)始循環(huán)，當(dāng)j=k-1且小于網(wǎng)中總頂點(diǎn)數(shù)時(shí)，權(quán)值小于無(wú)窮則將此權(quán)值付給min,并令邊m=j。（5）重新修改樹(shù)邊的距離，將原來(lái)的邊用權(quán)值小的邊替換，若當(dāng)前邊k小于n(原定邊數(shù))，則令tl=t.ct[i].endvex，w=t.s[j][tl]，若w<t.ct[i].weight，則令t.ct[i].weight=w，t.ct[i].fromvex=j。（6）最后利用for循環(huán)鍵入每條邊的起始點(diǎn)，終結(jié)點(diǎn)及邊上的權(quán)值。函數(shù)：classtree{public:ints[n+1][n+1];//網(wǎng)的鄰接矩陣

edgesetct[n+1];//最小生成樹(shù)的邊集

voidprim(tree&t);//普里姆算法

};10XXXvoidtree::prim(tree&t){inti,j,k,min,tl,m,w;//k為當(dāng)前頂點(diǎn)數(shù),m為當(dāng)前邊數(shù),w為當(dāng)前權(quán)值for(i=1;i<n;i++)//從頂點(diǎn)1出發(fā)求最小生成樹(shù)的邊{t.ct[i].fromvex=1;t.ct[i].endvex=i+1;t.ct[i].weight=t.s[1][i+1];}for(k=2;k<=n;k++){min=32767;m=k-1;for(j=k-1;j<n;j++)//找權(quán)值最小的樹(shù)邊if(t.ct[j].weight<min){min=t.ct[j].weight;m=j;}edgesettemp=t.ct[k-1];t.ct[k-1]=t.ct[m];t.ct[m]=temp;j=t.ct[k-1].endvex;for(i=k;i<n;i++)//重新修改樹(shù)邊的距離{tl=t.ct[i].endvex;w=t.s[j][tl];if(w<t.ct[i].weight)//原來(lái)的邊用權(quán)值較小的邊取代{t.ct[i].weight=w;t.ct[i].fromvex=j;}

}}11XXX}附錄：主函數(shù)voidmain(){intz;for(z=1;z<=3;z++){cout<<"*************請(qǐng)選擇一種算法*****************"<<endl;cout<<"1.prim算法求解最小生成樹(shù)"<<endl;cout<<"2.kruskal算法求解最小生成樹(shù)"<<endl;cin>>z;if(z==1){intj,w;treet;cout<<"——prim算法求最小生成樹(shù)——"<<endl;cout<<"請(qǐng)連續(xù)輸入網(wǎng)的10條邊"<<endl;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(i==j)t.s[i][j]=0;elset.s[i][j]=32767;//i,j）邊上無(wú)權(quán)值，用32767來(lái)代替無(wú)窮for(intk=1;k<=e;k++)//建立網(wǎng)的鄰接矩陣{cout<<"請(qǐng)輸入一條邊的起始點(diǎn)，終結(jié)點(diǎn)及邊上的權(quán)值：";cin>>i>>j>>w;cout<<endl;t.s[i][j]=w;t.s[j][i]=w;}t.prim(t);//用普里姆算法求最小生成樹(shù)cout<<":"<<endl;12XXXfor(i=1;i<n;i++)//輸出n-1條生成樹(shù)的邊{cout<<t.ct[i].fromvex<<"";cout<<t.ct[i].endvex<<"";cout<<t.ct[i].weight<<endl;}}else{//kruskaltree2t2;cout<<"——kruskal算法求最小生成樹(shù)——"<<endl;cout<<"請(qǐng)連續(xù)輸入網(wǎng)的10條邊(按權(quán)值從小到大的順序)"<<endl;for(inti=1;i<=e;i++){cout<<"輸入一條邊的起始邊，終止邊以及權(quán)值:";cin>>t2.ge2[i].fromvex>>t2.ge2[i].endvex>>t2.ge2[i].weigh