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

《实验报告：图的存储结构和遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、ualC++6.04．实验方法和步骤（含设计）我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可知，其邻接矩阵示意图为如下：V0v1v2v3v4v5V0010101V1101110V2010010V3110011V4011100V5100100此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：5．程序及测试结果#include#includeintvisited[6];typedefstruct{inta[6][6];intn;}mgraph;typedefstructAN

3、ode{intadjvex;structANode*nextarc;}ArcNode;typedefstructVnode{ArcNode*firstarc;}VNode;typedefVNodeAdjList[6];typedefstruct{AdjListadjlist;intn;}ALGraph;voidmattolist(mgraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i

4、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;}voiddispadj(ALGraph*G){inti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%d",p->adjvex

5、);p=p->nextarc;}printf("");}}voiddfs(ALGraph*G,intv){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;}}voidbfs(ALGraph*G,intv){ArcNode*p;intqueue[6],front=0,rear=0;intvisited[6];intw,i;for(i=0;in;i++)visite

6、d[i]=0;printf("%d",v);visited[v]=1;rear=(rear+1)%6;queue[rear]=v;while(front!=rear){front=(front+1)%6;w=queue[front];p=G->adjlist[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%6;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("");}in

7、tmain(){mgraphg;ALGraph*G;inta[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}};inti,j;g.n=6;for(i=0;i