实验分析报告：图的存储结构和遍历

1、实验报告：图的存储结构和遍历 作者: 日期: 武汉东湖学院 实验报告 姓名 付磊 学 号 2015040131042 班级 计科一班 指导老师 吴佳芬 课程名称 数据结构 成 实验名称 图的存储结构和遍历 绩 学院：计算机科学学院 专业 计算机科学与技术 2016年 11月 18日 1 .实验目的 (1) 了解邻接矩阵存储法和邻接表存储法的实现过程。 (2) 了解图的深度优先遍历和广度优先遍历的实现过程。 2 .实验内容 1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵 2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法 3. 实现基

2、于第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 此时的 a 1” 表示这两个节点有关系， “0”表示这两个节点无关系 我们通过邻接表来在计算机中

3、存储图时，其邻接表存储图如下: 0 4 卜 申 | 1 ”5 3 A WI 9 却- 3 T呂|A 1 1卜 5 Ts lAl 丄11号 12 5 .程序及测试结果X # include # include int visited 6; typedef struct int a66; int n; mgraph; typedef struct ANode int adjvex; struct ANode *nextarc; ArcNode; typedef struct Vnode ArcNode *firstarc; VNode; typedef VNode AdjList 6; typed

4、ef struct AdjList adjlist; int n; ALGraph; void mattolist (mgraph g,ALGraph * ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(g.aij!=0) p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=g.n; v

5、oid dispadj(ALGraph *G) int i; ArcNode *p; for(i=0;in;i+) p=G-adjlisti.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-adjlistv.firstarc; while (p!=NULL) if(visitedp-adjvex=0) dfs(G,p-adjv

6、ex); p=p-nextarc; void bfs (ALGraph *G ,int v) ArcNode *p; int queue6,front=0,rear=0; int visited6; int w,i; for(i=0;in;i+) visitedi=0; printf(%d ,v); visitedv=1; rear=(rea 叶1)%6; queuerear=v; while (front!=rear) front=(front+1)%6; w=queuefront; p=G-adjlistw.firstarc; while(p!=NULL) if(visitedp-adjv

7、ex=0) printf(%d ,p-adjvex); visitedp-adjvex=1; rear=(rea 叶1)%6; queuerear=p-adjvex; p=p_nextarc; printf(n); int main () mgraph g; ALGraph *G; int a66=0,1,0,1,0,1,1,0,1,1,1,0,0,1,0,0,1,0, 1,1,0,0,1,1,0,1,1,1,0,0,1,0,0,1,0,0; int i,j; g.n=6; for(i=0;ig.n;i+) for(j=0;jvg.n;j+) g.aij=aij; for(i=0;ig.n;i

8、+) for(j=0;jg.n;j+) printf(%d ,g.aij); printf(n); printf(邻接矩阵n); G=(ALGraph*)malloc(sizeof(ALGraph); mattolist(g,G); dispadj(G); printf(令B接表n); dfs(G,0); printf(n); printf( 从0开始的深度优先遍历 n); bfs(G,0); printf(n); printf( 从0开始的广度优先遍历 n); return 0; 6 .实验分析与体会 通过此次实验，使我更加深刻的明白了图在计算机中是如何存储的， 图在计算机中的存储有两种，一种是邻接矩阵存储方式，这种方式我 们主要是运用到了二维数组的特性，通过二维数组来明确表现出节点 与节点的位置关系，第二种就是我们说的邻接表存储结构，这种结构 主要是运用到了指针来实现。而当我们在进行图的遍历时，首先要选 择一个起始点，上面我们选择的是0为起始点，当我们在进行深度优 先遍历时，可以用递归的思想，而在广度优先遍历时，不能用递归， 这个要注意。 在这次的实验中，通过对图的操作