圖的遍歷-實驗報告

-.z.洛陽理工學(xué)院實驗報告系別計算機(jī)系班級**課程名稱數(shù)據(jù)構(gòu)造實驗日期實驗名稱圖的遍歷成績實驗?zāi)康模?.掌握圖的構(gòu)造特征，以及鄰接矩陣和鄰接表存儲構(gòu)造的特點(diǎn)和實現(xiàn)。2.掌握在鄰接矩陣或鄰接表存儲構(gòu)造下列圖的深度優(yōu)先和廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實驗條件：計算機(jī)一臺，VisualC++6.0實驗內(nèi)容：問題描述以鄰接矩陣或鄰接表為存儲構(gòu)造，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法遍歷一個無向圖。給出遍歷序列，假設(shè)該圖不連通，給出其連通分量的個數(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)立隊列：voidInitQueue(LinkQueue&Q)〔4〕主函數(shù)：voidmain()詳細(xì)設(shè)計#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("請輸入結(jié)點(diǎn)個數(shù)："); scanf("%c",G.ve*num); printf("請輸入弧的個數(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("請輸入與結(jié)點(diǎn)%d相鄰的邊數(shù)：",&k); scanf("%d",&v2); printf("請輸入與第%d個結(jié)點(diǎn)相連的結(jié)點(diǎn)編號：",&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("請輸入與第%d個結(jié)點(diǎn)相連的結(jié)點(diǎn)編號：",&k); scanf("%d",&m);ArcNode*q;q=(ArcNode*)malloc(sizeof(ArcNode));//動態(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)//建立一個空隊列{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)隊{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)//出隊{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)//判斷隊列是否為空{(diào)if(Q.front==Q.rear)return1;return0;}intmain(){inti;ALGraphG;CreateDG(G);int*;printf("請輸入結(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("請輸入第一個要訪問的結(jié)點(diǎn)序號：\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個連通分量!\n");return0;}5.測試數(shù)據(jù)及結(jié)果給出2組以上的