數(shù)據(jù)結(jié)構(gòu)圖的遍歷實驗報告

1、實驗項目名稱：圖的遍歷一、實驗?zāi)康膽?yīng)用所學(xué)的知識分析問題、解決問題，學(xué)會用建立圖并對其進行 遍歷，提高實際編程能力及程序調(diào)試能力。二、實驗內(nèi)容問題描述：建立有向圖，并用深度優(yōu)先搜索和廣度優(yōu)先搜素。輸 入圖中節(jié)點的個數(shù)和邊的個數(shù)，能夠打印由用鄰接表或鄰接矩陣表示 的圖的儲存結(jié)構(gòu)。三、實驗儀器與設(shè)備計算機，Code:Blocks 。四、實驗原理用鄰接表存儲一個圖，遞歸方法深度搜索和用隊列進行廣度搜索, 并輸由遍歷的結(jié)果。五、實驗程序及結(jié)果#define INFINITY 10000 /* 無窮大 */#define MAX_VERTEX_NUM 40#define MAX 40#include&l

2、t;stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedef 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(MGrap

3、h *G,char* v) int c = -1,i;for(i=0;i<G->vexnum;i+)if(strcmp(v,G->)=0) c=i; break;return c;MGraph * CreatUDN(MGraph *G)/初始化圖，接受用戶輸入 int i,j,k,w;char v120,v220;printf("請輸入圖的頂點數(shù)，弧數(shù):")；scanf("%d%d",&G->vexnum,&G->arcnum);printf("結(jié)點名字:n");for

4、(i=0;i<G->vexnum;i+)printf("No.%d:",i+1);scanf("%s”,G->);for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)G->arcsij.adj=INFINITY;printf("請輸入一條邊依附的兩個頂點和權(quán)值：n");for(k=0;k<G->arcnum;k+)printf("第陳邊:n",k+1);printf("起始結(jié)點:");s

5、canf("%s",v1);printf(" 結(jié)束結(jié)點:");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->arcs皿i=G->arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i;if(v<

6、=0 && v<G->vexnum) /v 合理for(i=0;i<G->vexnum;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 && v<G->vexnum && w>=0 && w&l

7、t;G->vexnum)v,w 合理for( k=w+1;k<G->vexnum;k+) if(G->arcsvk.adj!=INFINITY) return k;return -1;int visitedMAX;void DFS(MGraph *G,int v)/ 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖Gint w;visitedv=1;VisitFunc(G,v);/ 訪問第v個結(jié)點for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w);printf("%d ”,G-

8、>arcsvw);void DFSTraverse(MGraph *G,char *s)/深度優(yōu)先遍歷int v,k;for(v=0;v<G->vexnum;v+)visitedv=0;k=LocateVex(G,s);if(k>=0&&k<G->vexnum)for(v=k;v>=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;v<G->vexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next

9、;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)

10、;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é)點不存在!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 Que

11、ueEmpty(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;v<G->vexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v>=0;v-)if(!Visitedv)Visitedv=1;VisitFunc

12、(G,v);EnQueue(&Q,v);/v 入隊while(!QueueEmpty(&Q)DeQueue(&Q,&u);/ 出隊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;v<G->vexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v 入隊while(!QueueEmpty(

13、&Q)DeQueue(&Q,&u);/ 出隊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("請輸入起始結(jié)點名稱：");scanf("%s",v);printf("n深度優(yōu)先遍歷:n");DFSTraverse(G,v);printf("n廣度優(yōu)先遍歷:n");BFSTraverse(G,v);getch()；六、實驗總結(jié)實驗要求輸入圖中節(jié)點的個數(shù)和邊的個數(shù)，能夠打印由用鄰接表 或鄰接矩陣表示的圖的儲存結(jié)構(gòu)。在設(shè)計中其中用鄰接表表示的節(jié)點 的值只能是數(shù)字，但用鄰接矩陣表示的節(jié)點的值可以是字母。但用鄰 接表形式要相對簡單一些。深度優(yōu)先采取的遞歸思想。首先，將從起點，沿某條邊，順勢遍 歷