圖的深度和廣度遍歷

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

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

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

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

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