中南大学数据结构实验报告3(图).doc

数据结构实验报告 班级：信安1401 姓名： 学号 实验日期：2015年12月 实验三 图的遍历 实验目的： 熟悉图的各种存储结构及构造算法； 熟练掌握图的两种搜索路径的遍历。 实验内容： 以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。 2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。 概要设计： 数据类型及函数定义 定义图 typedef struct{ int V[M]; int R[M][M]; int vexnum; }Graph; 创建图 void creatgraph(Graph *g,int n) 打印图的邻接矩阵 void printgraph(Graph *g) 访问顶点 void visitvex(Graph *g,int vex) 深度递归遍历 void dfs(Graph *g,int vex) 队列的基本操作 定义队列 typedef struct{ int V[M]; int front; int rear; }Queue; 判断队列是否为空 quempty(Queue *q) 入队操作 enqueue(Queue *q,int e) 出队操作 dequeue(Queue *q) 广度遍历 void BESTraverse(Graph *g) 本程序包含四个模块： 主程序模块 void main () {构造一个图; 打印图的邻接矩阵 进行深度优先遍历图; 进行广度优先遍历图;}; 详细设计： #define M 20 #include stdio.h #include stdlib.h #include malloc.h /*定义图*/ typedef struct{ int V[M]; int R[M][M]; int vexnum; }Graph; /*创建图*/ void creatgraph(Graph *g,int n) { int i,j,r1,r2; g-vexnum=n; /*顶点用i表示*/ for(i=1;i=n;i++) { g-V[i]=i; } /*初始化R*/ for(i=1;i=n;i++) for(j=1;j=n;j++) { g-R[i][j]=0; } /*输入R*/ printf(Please input R(0,0 END):\n); scanf(%d,%d,r1,r2); while(r1!=0r2!=0) { g-R[r1][r2]=1; g-R[r2][r1]=1; scanf(%d,%d,r1,r2); } } /*打印图的邻接矩阵*/ void printgraph(Graph *g) { int i,j; for(i=1;i=g-vexnum;i++) { for(j=1;j=g-vexnum;j++) { printf(%2d ,g-R[i][j]); } printf(\n); }} /*全局变量：访问标志数组*/ int visited[M]; /*访问顶点*/ void visitvex(Graph *g,int vex) { printf(%d ,g-V[vex]); } /*获取第一个未被访问的邻接节点*/ int firstadjvex(Graph *g,int vex) { int w,i; for(i=1;i=g-vexnum;i++) { if(g-R[vex][i]==1visited[i]==0) { w=i; break; } else { w=0; } } return w; } /*获取下一个未被访问的邻接节点(深度遍历)*/ int nextadjvex(Graph *g,int vex,int w) { int t; t=firstadjvex(g,w); return t; } /*深度递归遍历*/ void dfs(Graph *g,int vex) { int w; visited[vex]=1;