图遍历操作实验报告

1、图遍历操作实验报告 实验报告 姓名： 班级： 12 南航网络 学号： 实验 题目 图的遍历操作 实验时间 2021-11-27 实验地点 指导教师 尚鲜莲 实验目的与要求： 目的：熟练掌握图的的两种存储结构；熟练掌握图的深度优先遍历和广度优先遍历算法；能解决简单的应用问题。 要求： 分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（dfs）和广度优先遍历（bfs）的操作。搞清楚 bfs 算法中队列的作用。 需求分析和实现功能说明： ： 在 test4.c 中填写入相应语句，使之能顺利完成图的深度优先和广度优先遍历操作。测试数据为：无向图 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); 上机调试情况说明（包括调试数据、调试过程中遇到的问