實(shí)驗(yàn)四：圖的遍歷

實(shí)驗(yàn)報(bào)告學(xué)院〔系〕名稱：計(jì)算機(jī)與通信工程學(xué)院姓名***學(xué)號(hào)***專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)〔中外合作〕班級(jí)2023級(jí)6班實(shí)驗(yàn)工程實(shí)驗(yàn)四：圖的遍歷課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼實(shí)驗(yàn)時(shí)間2023年12月11日實(shí)驗(yàn)地點(diǎn)計(jì)算機(jī)根底實(shí)驗(yàn)室210批改意見成績教師簽字：實(shí)驗(yàn)?zāi)康模豪斫鈭D的邏輯特點(diǎn)；掌握理解圖的兩種主要存儲(chǔ)結(jié)構(gòu)〔鄰接矩陣和鄰接表〕，掌握?qǐng)D的構(gòu)造、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。具體實(shí)驗(yàn)題目：每位同學(xué)按下述要求實(shí)現(xiàn)相應(yīng)算法：根據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)立圖〔圖的存儲(chǔ)結(jié)構(gòu)可采用鄰接矩陣或鄰接表〕，并對(duì)圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索〔實(shí)驗(yàn)類型：驗(yàn)證型〕1〕問題描述：在主程序中提供以下菜單： 1…圖的建立 2…深度優(yōu)先遍歷圖 3…廣度優(yōu)先遍歷圖 0…結(jié)束2〕實(shí)驗(yàn)要求：圖的存儲(chǔ)可采用鄰接表或鄰接矩陣；定義以下過程：CreateGraph():按從鍵盤的數(shù)據(jù)建立圖DFSGrahp()：深度優(yōu)先遍歷圖BFSGrahp()：廣度優(yōu)先遍歷圖【實(shí)驗(yàn)過程記錄〔源程序、測試用例、測試結(jié)果及心得體會(huì)等〕】實(shí)驗(yàn)源程序如下#include<stdio.h>#include<stdlib.h>#defineMAX10//最大定點(diǎn)數(shù)typedefstructQNode//定義隊(duì)列{ intdata; structQNode*next;}QNode;typedefstruct{ QNode*front; QNode*rear;}Queue;typedefstructArcNode//連接表構(gòu)建圖{ intadjvex; structArcNode*nextarc;}ArcNode;typedefstructVNode//頭結(jié)點(diǎn){ chardata; ArcNode*firstarc;//鄰接鏈表頭指針}VNode;typedefstruct{ VNodeadjlist[MAX]; intv,a;//圖的頂點(diǎn)數(shù)和邊數(shù)}Graph;intInitQueue(Queue*s)//構(gòu)造一個(gè)空的對(duì)列{ s->front=s->rear=(QNode*)malloc(sizeof(QNode)); if(!s->front) return(0); s->front->next=NULL; return1;}Enqueue(Queue*s,inte)//入隊(duì)列{ QNode*p; p=(QNode*)malloc(sizeof(QNode)); if(!p)return(0); p->data=e; p->next=NULL; s->rear->next=p; s->rear=p; return1;}DEQueue(Queue*q,int*e)//出隊(duì)列{ QNode*p; if(q->front==q->rear)return1;//表示這是空對(duì)列 { p=q->front->next; *e=p->data;//附值 q->front->next=p->next; } if(q->rear==p)q->rear=q->front; free(p); return1;}intemptyQueue(Queue*q)//判斷隊(duì)列是否為空{(diào) if(q->front==q->rear) return1; else return0;}voidCrerateGraph(Graph*G)//創(chuàng)立圖{ inti,m,n; ArcNode*p; printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):"); scanf("%d%d",&G->v,&G->a); getchar(); printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的信息:",G->v); for(i=0;i<G->v;i++) { scanf("%s",&G->adjlist[i].data);/*讀入頂點(diǎn)信息*/ G->adjlist[i].firstarc=NULL;/*邊表置為空表*/ } for(i=0;i<G->a;i++) { printf("輸入第%d條邊(起點(diǎn)序號(hào)，終點(diǎn)序號(hào)):",i+1); scanf("%d%d",&m,&n);//輸入無序?qū)旤c(diǎn)編號(hào)0開始 p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=n; p->nextarc=G->adjlist[m].firstarc; G->adjlist[m].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=m; p->nextarc=G->adjlist[n].firstarc; G->adjlist[n].firstarc=p; }}intvisited[MAX];voidDFSGraph(GraphG,inti)//深度優(yōu)先遍歷{ ArcNode*p; printf("訪問頂點(diǎn):%c\n",G.adjlist[i].data);/*訪問頂點(diǎn)i*/ visited[i]=1; p=G.adjlist[i].firstarc; while(p)/*從p的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索*/ {if(!visited[p->adjvex]) DFSGraph(G,p->adjvex); p=p->nextarc;//找指向下一條弧的指針 }}voidDFSTraverse(GraphG){inti;for(i=0;i<G.v;i++)visited[i]=0;/*初始化標(biāo)志數(shù)組*/for(i=0;i<G.v;i++)if(!visited[i])/*vi未訪問過*/DFSGraph(G,i);//函數(shù)的遞歸的使用}intvisit[MAX];voidBFSGraph(GraphG)//廣度優(yōu)先遍歷{ inti,k; Queueq; ArcNode*p; for(i=0;i<G.v;i++); visit[i]=0; InitQueue(&q); for(i=0;i<G.v;i++) if(!visit[i]) { printf("訪問頂點(diǎn):%c\n",G.adjlist[i].data); visit[i]=1; Enqueue(&q,i); while(!emptyQueue(&q)) { DEQueue(&q,&k); p=G.adjlist[k].firstarc; while(p) { if(!visited[p->adjvex]) { printf("訪問頂點(diǎn):%c\n",G.adjlist[p->adjvex].data); visited[p->adjvex]=1; Enqueue(&q,p->adjvex); } p=p->nextarc; } } }}voidmain()//主程序{ inta,i,j; Graph*G;G=(Graph*)malloc(sizeof(Graph)); while(a) { printf("請(qǐng)輸入1~4，運(yùn)行其功能\n"); printf("1……圖的建立(本程序最多包含的點(diǎn)數(shù)為10)\n"); printf("2……深度優(yōu)先遍歷圖\n"); printf("3……廣度優(yōu)先遍歷圖\n"); printf("4……結(jié)束\n"); scanf("%d",&a); getchar(); switch(a){ case1: CrerateGraph(G);break; case2: DFSTraverse(*G);break; case3:BFSGraph(*G);break; default:exit(4); } }}測試用例及測試結(jié)果如下：深度優(yōu)先遍歷輸出結(jié)果：13542廣度優(yōu)先遍歷輸出結(jié)果：12345實(shí)驗(yàn)設(shè)計(jì)思路：〔1〕圖的創(chuàng)立我采用的是連接表儲(chǔ)存結(jié)構(gòu)，將圖的頂點(diǎn)、邊的信息分別存在連接表的data