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

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

2、验环境Visual C+ 6.04实验方法和步骤含设计我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可知，其邻接矩阵示意图为如下：V0 v1 v2 v3 v4 v5V00 1 0 1 0 1V1 1 0 1 1 1 0V2 0 1 0 0 1 0V3 1 1 0 0 1 1V4 0 1 1 1 0 0V5 1 0 0 1 0 0此时的1表示这两个节点有关系，0表示这两个节点无关系。 我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：5程序及测试结果# include # include int visited 6;typedef struct int a66; int n;m

3、graph;typedef struct ANode int adjve*;struct ANode *ne*tarc;Arode;typedef struct Vnode Arode *firstarc;VNode;typedef VNode AdjList6;typedef struct AdjList adjlist; int n;ALGraph;void mattolist (mgraph g,ALGraph *&G) int i,j; Arode *p; G=(ALGraph*)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NU

4、LL; for(i=0;i=0;j-) if(g.aij!=0) p=(Arode*)malloc(sizeof(Arode); p-adjve*=j; p-ne*tarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=g.n;void dispadj(ALGraph *G) int i; Arode *p;for(i=0;in;i+) p=G-adjlisti.firstarc; printf(%d:,i); while (p!=NULL) printf(%d ,p-adjve*); p=p-ne*tarc; printf(n);void d

5、fs (ALGraph *G,int v)Arode *p;visited v=1;printf(%d ,v);p=G-adjlistv.firstarc;while (p!=NULL) if(visitedp-adjve*=0) dfs(G,p-adjve*); p=p-ne*tarc; void bfs (ALGraph *G ,int v) Arode *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=(rear+

6、1)%6; queuerear=v; while (front!=rear) front=(front+1)%6; w=queuefront; p=G-adjlistw.firstarc; while(p!=NULL) if(visitedp-adjve*=0) printf(%d ,p-adjve*); visitedp-adjve*=1; rear=(rear+1)%6; queuerear=p-adjve*; p=p-ne*tarc; printf(n);int main ()mgraph g;ALGraph *G;int a66=0,1,0,1,0,1,1,0,1,1,1,0,0,1,

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