圖的遍歷-實(shí)驗(yàn)報(bào)告

-.z.洛陽(yáng)理工學(xué)院實(shí)驗(yàn)報(bào)告系別計(jì)算機(jī)系班級(jí)**課程名稱數(shù)據(jù)構(gòu)造實(shí)驗(yàn)日期實(shí)驗(yàn)名稱圖的遍歷成績(jī)實(shí)驗(yàn)?zāi)康模?.掌握?qǐng)D的構(gòu)造特征，以及鄰接矩陣和鄰接表存儲(chǔ)構(gòu)造的特點(diǎn)和實(shí)現(xiàn)。2.掌握在鄰接矩陣或鄰接表存儲(chǔ)構(gòu)造下列圖的深度優(yōu)先和廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)條件：計(jì)算機(jī)一臺(tái)，VisualC++6.0實(shí)驗(yàn)內(nèi)容：?jiǎn)栴}描述以鄰接矩陣或鄰接表為存儲(chǔ)構(gòu)造，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法遍歷一個(gè)無(wú)向圖。給出遍歷序列，假設(shè)該圖不連通，給出其連通分量的個(gè)數(shù)和各連通分量的遍歷序列。數(shù)據(jù)構(gòu)造類型定義typedefintInfoType;typedefstructArcNode{intadjve*;structArcNode*ne*tarc;}ArcNode;typedefstructVNode{intdata;ArcNode*firstarc;}VNode,AdjList[MA*_VERTE*_NUM];typedefstruct{AdjListvertices;intve*num,arcnum;intkind;}ALGraph;模塊劃分〔1〕創(chuàng)立鄰接表：voidCreateDG〔ALGraph&G〕〔2〕深度搜索算法：voidDFS(ALGraphG,intv)〔3〕創(chuàng)立隊(duì)列：voidInitQueue(LinkQueue&Q)〔4〕主函數(shù)：voidmain()詳細(xì)設(shè)計(jì)#include<stdio.h>#include<string.h>#include<malloc.h>#include<conio.h>intvisited[30];#defineMA*_VERTE*_NUM30#defineOK1typedefintInfoType;typedefstructArcNode//弧{intadjve*;structArcNode*ne*tarc;}ArcNode;typedefstructVNode//表頭{intdata;ArcNode*firstarc;}VNode,AdjList[MA*_VERTE*_NUM];typedefstruct//圖{AdjListvertices;intve*num,arcnum;intkind;}ALGraph;voidCreateDG(ALGraph&G){intk,i,v1; printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)："); scanf("%c",G.ve*num); printf("請(qǐng)輸入弧的個(gè)數(shù)："); scanf("%c",G.arcnum);for(i=1;i<=G.ve*num;i++){G.vertices[i].data=i;G.vertices[i].firstarc=NULL;}for(k=1;k<=G.ve*num;k++)//輸入邊{intv2; printf("請(qǐng)輸入與結(jié)點(diǎn)%d相鄰的邊數(shù)：",&k); scanf("%d",&v2); printf("請(qǐng)輸入與第%d個(gè)結(jié)點(diǎn)相連的結(jié)點(diǎn)編號(hào)：",&k); scanf("%d",&v1);ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)e*it(-1);p->adjve*=v1;p->ne*tarc=NULL;G.vertices[k].firstarc=p;for(inti=1;i<v2;i++){intm; printf("請(qǐng)輸入與第%d個(gè)結(jié)點(diǎn)相連的結(jié)點(diǎn)編號(hào)：",&k); scanf("%d",&m);ArcNode*q;q=(ArcNode*)malloc(sizeof(ArcNode));//動(dòng)態(tài)指針if(!q)e*it(-1);q->adjve*=m;//頂點(diǎn)給Pq->ne*tarc=NULL;p->ne*tarc=q;p=q;}}}voidDFS(ALGraphG,intv)//深度搜索{visited[v]=1;printf("%c",G.vertices[v].data);ArcNode**;*=(ArcNode*)malloc(sizeof(ArcNode));if(!*)e*it(-1);*=G.vertices[v].firstarc;intw;for(;*;*=*->ne*tarc){w=*->adjve*;if(visited[w]==0)DFS(G,w);}}typedefstructQNode{intdata;QNode*ne*t;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue&Q)//建立一個(gè)空隊(duì)列{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)e*it(-1);Q.front->ne*t=NULL;}voidEnQueue(LinkQueue&Q,inte)//進(jìn)隊(duì){QNode*p;p=(QNode*)malloc(sizeof(QNode));if(!p)e*it(-1);p->data=e;p->ne*t=NULL;Q.rear->ne*t=p;Q.rear=p;}intDeQueue(LinkQueue&Q,int&e)//出隊(duì){if(Q.front==Q.rear)return-1;QNode*p;p=(QNode*)malloc(sizeof(QNode));if(!p)e*it(-1);p=Q.front->ne*t;e=p->data;Q.front->ne*t=p->ne*t;if(Q.rear==p)Q.rear=Q.front;free(p);returne;}intQueueEmpty(LinkQueueQ)//判斷隊(duì)列是否為空{(diào)if(Q.front==Q.rear)return1;return0;}intmain(){inti;ALGraphG;CreateDG(G);int*;printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)：");scanf("%d",&*);printf("鄰接表為：\n");for(intj=1;j<=*;j++){printf("%c",G.vertices[j].data);ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));if(!p) e*it(-1);p=G.vertices[j].firstarc;while(p){printf("%c",p->adjve*);p=p->ne*tarc;}printf("\n");}printf("請(qǐng)輸入第一個(gè)要訪問(wèn)的結(jié)點(diǎn)序號(hào)：\n");intn;scanf("%d",&n);for(i=0;i<30;i++)visited[i]=0;printf("深度搜索：\n");DFS(G,n);for(i=0;i<30;i++)visited[i]=0;printf("該圖不連通!");printf("該圖有%d個(gè)連通分量!\n");return0;}5.測(cè)試數(shù)據(jù)及結(jié)果給出2組以上的