实验报告：图的存储结构和遍历.doc

武汉东湖学院 实 验 报 告 学院： 计算机科学学院 专业 计算机科学与技术 2016年 11月18日 姓 名 付磊 学 号 2015040131042 班 级 计科一班 指导老师 吴佳芬 课程名称 数据结构 成 绩 实验名称 图的存储结构和遍历 1．实验目的 （1）了解邻接矩阵存储法和邻接表存储法的实现过程。 （2）了解图的深度优先遍历和广度优先遍历的实现过程。 2．实验内容 1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵. 2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法 3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列 4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列 3．实验环境 Visual C++ 6.0 4．实验方法和步骤（含设计） 我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可知，其邻接矩阵示意图为如下： V0 v1 v2 v3 v4 v5 V0 0 1 0 1 0 1 V1 1 0 1 1 1 0 V2 0 1 0 0 1 0 V3 1 1 0 0 1 1 V4 0 1 1 1 0 0 V5 1 0 0 1 0 0 此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。 我们通过邻接表来在计算机中存储图时，其邻接表存储图如下： 5．程序及测试结果 # include stdio.h # include malloc.h int visited [6]; typedef struct { int a[6][6]; int n; }mgraph; typedef struct ANode { int adjvex; struct ANode *nextarc; }ArcNode; typedef struct Vnode { ArcNode *firstarc; }VNode; typedef VNode AdjList[6]; typedef struct { AdjList adjlist; int n; }ALGraph; void mattolist (mgraph g,ALGraph *G) { int i,j; ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;ig.n;i++) G-adjlist[i].firstarc=NULL; for(i=0;ig.n;i++) for(j=g.n-1;j=0;j--) if(g.a[i][j]!=0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p-adjvex=j; p-nextarc=G-adjlist[i].firstarc; G-adjlist[i].firstarc=p; } G-n=g.n; } void dispadj(ALGraph *G) { int i; ArcNode *p; for(i=0;iG-n;i++) { p=G-adjlist[i].firstarc; printf(%d:,i); while (p!=NULL) { printf(%d ,p-adjvex); p=p-nextarc; } printf(\n); } } void dfs (ALGraph *G,int v) { ArcNode *p; visited [v]=1; printf(%d ,v); p=G-adjlist[v].firstarc; while (p!=NULL) { if(visited[p-adjvex]==0) dfs(G,p-adjvex); p=p-nextarc; } } void bfs (ALGraph *G ,int v) { ArcNode *p; int queue[6],front=0,rear=0; int visited[6]; int w,i; for(i=0;iG-n;i++) visited[i]=0; printf(%d ,v); visited[v]=1; rear