武汉东湖学院实验报告
学院:
计算机科学学院专业计算机科学与技术2016年11月18日
姓名付磊学号 2
班级计科一班指导老师吴佳芬
课程名称数据结构成
绩
实验名称图的存储结构与遍历
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”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时,其邻接表存储图如下:
ALGraph *G;
int a[6][6]={{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;i<g、n;i++)
for(j=0;j<g、n;j++)
g、a[i][j]=a[i][j];
for(i=0;i<g、n;i++)
{ for(j=0;j<g、n;j++)
printf("%d ",g、a[i][j]);
printf("\n");
}
printf("----------邻接矩阵----------\n");
G=(ALGraph*)malloc(sizeof(ALGraph));
mattolist(g,G);
dispadj(G);
printf("----------邻接表-------------\n");
dfs(G,0);
printf("\n");
printf("-----------从0开始的深度优先遍历-------------\n");
bfs(G,0);
printf("\n");
printf("-----------从0开始的广度优先遍历--------------\n");
return 0;
}。