數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報(bào)告

.實(shí)驗(yàn)項(xiàng)目名稱： 圖的遍歷 一、實(shí)驗(yàn)?zāi)康?應(yīng)用所學(xué)的知識(shí)分析問(wèn)題、解決問(wèn)題，學(xué)會(huì)用建立圖并對(duì)其進(jìn)行遍歷，提高實(shí)際編程能力及程序調(diào)試能力。二、實(shí)驗(yàn)內(nèi)容 問(wèn)題描述：建立有向圖，并用深度優(yōu)先搜索和廣度優(yōu)先搜素。輸入圖中節(jié)點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)，能夠打印出用鄰接表或鄰接矩陣表示的圖的儲(chǔ)存結(jié)構(gòu)。三、實(shí)驗(yàn)儀器與設(shè)備 計(jì)算機(jī)，Code:Blocks。四、實(shí)驗(yàn)原理 用鄰接表存儲(chǔ)一個(gè)圖，遞歸方法深度搜索和用隊(duì)列進(jìn)行廣度搜索，并輸出遍歷的結(jié)果。5、 實(shí)驗(yàn)程序及結(jié)果#define INFINITY 10000 /*無(wú)窮大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef struct ArCellint adj; ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char name20; infotype;typedef struct infotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph *G,char* v) int c = -1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-)=0) c=i; break;return c;MGraph * CreatUDN(MGraph *G)/初始化圖，接受用戶輸入int i,j,k,w;char v120,v220;printf(請(qǐng)輸入圖的頂點(diǎn)數(shù),弧數(shù):);scanf(%d%d,&G-vexnum,&G-arcnum);printf(結(jié)點(diǎn)名字:n);for(i=0;ivexnum;i+)printf(No.%d:,i+1);scanf(%s,G-);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(請(qǐng)輸入一條邊依附的兩個(gè)頂點(diǎn)和權(quán)值:n);for(k=0;karcnum;k+)printf(第%d條邊:n,k+1); printf(起始結(jié)點(diǎn):);scanf(%s,v1); printf(結(jié)束結(jié)點(diǎn):);scanf(%s,v2); /printf(邊的權(quán)值:); /scanf(%d,&w);i=LocateVex(G,v1); j=LocateVex(G,v2);if(i=0&j=0)/G-arcsij.adj=w;G-arcsji=G-arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i;if(v=0 & vvexnum) /v合理for(i=0;ivexnum;i+)if(G-arcsvi.adj!=INFINITY)return i;return -1;void VisitFunc(MGraph *G,int v)printf(%s ,G-);int NextAdjVex(MGraph *G,int v,int w)int k;if(v=0 & vvexnum & w=0 & wvexnum)/v,w合理for( k=w+1;kvexnum;k+)if(G-arcsvk.adj!=INFINITY)return k;return -1;int visitedMAX;void DFS(MGraph *G,int v)/從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖Gint w;visitedv=1;VisitFunc(G,v);/訪問(wèn)第v個(gè)結(jié)點(diǎn)for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);printf(%d ,G-arcsvw);void DFSTraverse(MGraph *G,char *s)/深度優(yōu)先遍歷int v,k;for(v=0;vvexnum;v+)visitedv=0;k=LocateVex(G,s);if(k=0&kvexnum)for(v=k;v=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;vvexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(0);Q-front-next=NULL;return 1;void EnQueue(LinkQueue *Q,int a )QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-vexnum=a;p-next=NULL;Q-rear-next=p;Q-rear=p;int DeQueue(LinkQueue *Q,int *v) QueuePtr p;if(Q-front=Q-rear)printf(結(jié)點(diǎn)不存在!n);exit(0);p=Q-front-next;*v=p-vexnum;Q-front-next=p-next;if(Q-rear=p)Q-front=Q-rear;return *v;int QueueEmpty(LinkQueue *Q)if(Q-rear=Q-front)return 0;return 1;int VisitedMAX;void BFSTraverse(MGraph *G,char *str)/廣度優(yōu)先遍歷int w,u,v,k;LinkQueue Q,q;for(v=0;vvexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v=0;v-)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入隊(duì)while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出隊(duì)for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);for(v=k+1;vvexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入隊(duì)while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出隊(duì)for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);void main()MGraph *G,b;char v10;G=CreatUDN(&b);printf(請(qǐng)輸入起始結(jié)點(diǎn)名稱:);scanf(%s,v);printf(n深度優(yōu)先遍歷:n);DFSTraverse(G,v);printf(n廣度優(yōu)先遍歷:n);BFSTraverse(G,v);getch();6、 實(shí)驗(yàn)總結(jié)實(shí)驗(yàn)要求輸入圖中節(jié)點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)，能夠打印出用鄰接表或鄰接矩陣表示的圖的儲(chǔ)存結(jié)構(gòu)。在設(shè)計(jì)中其中用鄰接表表示的節(jié)點(diǎn)的值只能是數(shù)字，但用鄰接矩陣表示的節(jié)點(diǎn)的值可以是字母。但用鄰接表形式要相對(duì)簡(jiǎn)單一些。深度優(yōu)先采取的遞歸思想。首先，將從起點(diǎn)，沿某條邊，順勢(shì)遍歷下去，直到不能繼續(xù)遍歷下去。這時(shí)，又從起點(diǎn)的另一結(jié)點(diǎn)開(kāi)始，遍歷下去。如