圖遍歷操作實驗報告

1、圖遍歷操作實驗報告 實驗報告 姓名： 班級： 12 南航網(wǎng)絡 學號： 實驗 題目 圖的遍歷操作 實驗時間 2021-11-27 實驗地點 指導教師 尚鮮蓮 實驗目的與要求： 目的：熟練掌握圖的的兩種存儲結構；熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；能解決簡單的應用問題。 要求： 分別采用鄰接矩陣和鄰接表存儲結構，完成圖的深度優(yōu)先遍歷（dfs）和廣度優(yōu)先遍歷（bfs）的操作。搞清楚 bfs 算法中隊列的作用。 需求分析和實現(xiàn)功能說明： ： 在 test4.c 中填寫入相應語句，使之能順利完成圖的深度優(yōu)先和廣度優(yōu)先遍歷操作。測試數(shù)據(jù)為：無向圖 gl，v=v0，v1，v2，v3，v4 ，e=(

2、v0，v3)，(v1，v2)，(v1，v3)，(v1，v4)，(v2，v4)，（v3，v4)，起始頂點為v0。 將空缺語句補充完整，并寫出輸出結果。 ） 算法設計（最好給出流程圖）： ： 算法程序（源程序代碼） #define vex_num 5 #define maxsize 10 #include stdio.h typedef char vextype; typedef struct vextype vexsvex_num; int arcsvex_numvex_num; mgraph; typedef struct vextype elemvex_num; int front,rear

3、; sueue; sueue q; int visitedvex_num=0; void creat_mgraph( mgraph *g,int e); void dfs_m( mgraph *g,int i); void bfs( mgraph *g,int k); void initqueue(sueue *sq); int enqueue(sueue *sq,vextype x); int delqueue(sueue *sq,vextype *y); int queueempty(sueue *sq); void main() int e,i,j; mgraph *g; printf(

4、qing shu ru wu xiang tu bian de shu mu); scanf(%d,e); creat_mgraph(g,e); printf(qing shu ru bian li de qi shi ding dian); scanf(%d,i); dfs_m(g,i); for (j=0;jvex_num;+j) visitedj=0; bfs(g,i); void creat_mgraph( mgraph *g,int e) int i,j,k; printf(shu ru ge ding dian xin xi：); for (i=0;ivex_num;+i) /*

5、scanf(%c,g-vexsi);*/ g-vexsi=getch(); for(i=0;ivex_num;+i) printf(%d %cn ,i,g-vexsi); /*getch();*/ for (i=0;ivex_num;+i) for (j=0;jvex_num;+j) g-arcsij=0; printf(shu ru ge bian de ding dian xu hao i,j：); for(k=0;ke;k+) scanf(%d,%d,i,j); g-arcsij=1;g-arcsji=1; /* creat_mgraph */ void dfs_m( mgraph *g

6、,int i) int j; printf(%3c,g-vexsi); visitedi=1; for (j=0;jvex_num;j+) if(g-arcsij=1) (!visitedj) dfs_m(g,j); /*dfs_m */ void bfs( mgraph *g,int k) int x,i,j; sueue *q; initqueue(q); printf(%3c,g-vexsk); visitedk=1; x=enqueue(q,g-vexsk); while(!queueempty(q) x=delqueue(q,g-vexsi); for(j=0;jvex_num;j+

7、) if(g-arcsij=1) (!visitedj) printf( %3c,g-vexsj); visitedj=1; x=enqueue(q, g-vexsj); /*bfs*/ void initqueue(sueue *sq) sq-front=sq-rear=0; /* initqueue*/ int enqueue(sueue *sq,vextype x) if( (sq-rear+1) % maxsize = sq-front) return 0; sq-elemsq-rear=x; sq-rear=(sq-rear+1) % maxsize; return 1; printf(sq-rear is :%dn,sq-rear); /* enqueue*/ int delqueue(sueue *sq,vextype *y) if(sq-front=sq-rear) return 0; *y=sq-elemsq-front; sq-front=(sq-front+1) % maxsize ; return 1; /* delqueue*/ int queueempty(sueue *sq) return (sq-front=sq-rear); 上機調試情況說明（包括調試數(shù)據(jù)、調試過程中遇到的問