數(shù)據(jù)結(jié)構(gòu)實驗---圖的儲存與遍歷.doc

《數(shù)據(jù)結(jié)構(gòu)實驗---圖的儲存與遍歷.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)　課程實驗報告　學(xué)號：姓名：實驗日期：2016.1.7實驗名稱：圖的存貯與遍歷一、實驗?zāi)康恼莆請D這種復(fù)雜的非線性結(jié)構(gòu)的鄰接矩陣和鄰接表的存儲表示，以及在此兩種常用存儲方式下深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)操作的實現(xiàn)。二、實驗內(nèi)容與實驗步驟題目1：對以鄰接矩陣為存儲結(jié)構(gòu)的圖進行DFS和BFS遍歷問題描述：以鄰接矩陣為圖的存儲結(jié)構(gòu)，實現(xiàn)圖的DFS和BFS遍歷?；疽螅航⒁粋€圖的鄰接矩陣表示，輸出頂點的一種DFS和BFS序列。測試數(shù)據(jù)：V0V1V4V3V2如圖所示題目2：對以鄰接表為存儲結(jié)構(gòu)的圖進行DFS和BFS遍歷問題描述：以鄰接表為圖的存儲結(jié)構(gòu)，實現(xiàn)圖的D

2、FS和BFS遍歷?；疽螅航⒁粋€圖的鄰接表存貯，輸出頂點的一種DFS和BFS序列。測試數(shù)據(jù)：如圖所示1∧∧∧010∧3∧3∧4∧V0V1V2V3V4三、附錄：在此貼上調(diào)試好的程序。#include#include#include#defineM100typedefstructnode{charvex[M][2];intedge[M][M];intn,e;}Graph;intvisited[M];Graph*Create_Graph(){Graph*GA;inti,j,k,w;GA=(Graph*)malloc(size

3、of(Graph));printf("請輸入矩陣的頂點數(shù)和邊數(shù)(用逗號隔開)：");scanf("%d,%d",&GA->n,&GA->e);printf("請輸入矩陣頂點信息：");for(i=0;in;i++)scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1]));for(i=0;in;i++)for(j=0;jn;j++)GA->edge[i][j]=0;for(k=0;ke;k++){printf("請輸入第%d條邊的頂點位置(i,j)和權(quán)值(用逗號隔開)：",k+1);scanf("%d

4、,%d,%d",&i,&j,&w);GA->edge[i][j]=w;}return(GA);}voiddfs(Graph*GA,intv){inti;printf("%c%c",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;for(i=0;in;i++)if(GA->edge[v][i]==1&&visited[i]==0)dfs(GA,i);}voidtraver(Graph*GA){inti;for(i=0;in;i++)visited[i]=0;for(i=0;in;i++)if(visited[i]

5、==0)dfs(GA,i);}voidbfs(Graph*GA,intv){intj,k,front=-1,rear=-1;intQ[M];printf("%c%c",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;rear=rear+1;Q[rear]=v;while(front!=rear){front=front+1;k=Q[front];for(j=0;jn;j++)if(GA->edge[k][j]==1&&visited[j]==0){printf("%c%c",GA->vex[j][0],GA->vex[j][1

6、]);visited[j]=1;rear=rear+1;Q[rear]=j;}}}voidtraver1(Graph*GA){inti;for(i=0;in;i++)visited[i]=0;for(i=0;in;i++)if(visited[i]==0)bfs(GA,i);}typedefstructNODE{intadjvex;structNODE*next;}ENode;typedefstructNODE1{charvex[2];ENode*first;}VexNode;typedefstructFS1{VexNodeGL[M];intbian,top;

7、}FS;FS*CreateGL(){FS*kk=(FS*)malloc(sizeof(FS));inti,j,k;ENode*s;printf("請輸入頂點數(shù)和邊數(shù)(用逗號隔開)：");scanf("%d,%d",&kk->top,&kk->bian);printf("請輸入頂點信息：");for(i=0;itop;i++){scanf("%s",kk->GL[i].vex);kk->GL[i].first=NULL;}printf("請輸入邊的信息(i,j)：