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

《实验报告：图的存储结构和遍历.pdf》由会员分享，可在线阅读，更多相关《实验报告：图的存储结构和遍历.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、遍历序列-word.zl.-3实验环境Visual C+6.0-word.zl.-4实验方法和步骤含设计我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可知，其邻接矩阵示意图为如下：V0 v1V00v2v3v4v510101V1 1V1 10 01 11 11 10 0V2 0V2 01 10 00 01 10 0V3 1V3 11 10 00 01 11 1V4 0V4 01 11 11 10 00 0V5 1V5 10 00 01 10 00 0此时的“1表示这两个节点有关系，“0表示这两个节点无关系。我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：-word.zl.-5

3、程序及测试结果#include#include int visited 6;typedef structint a66;int n;mgraph;typedef struct ANodetypedef struct Vnodetypedef VNode AdjList6;typedef structAdjList 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=NULL;fo

4、r(j=g.n-1;j=0;j-)if(g.aij!=0)p=(Arode*)malloc(sizeof(Arode);p-adjvex=j;G-n=g.n;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p;for(i=0;ig.n;i+).-int i;Arode*p;void dfs(ALGraph*G,int v)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(

5、%d,v);visitedv=1;rear=(rear+1)%6;queuerear=v;while(front!=rear)front=(front+1)%6;w=queuefront;p=G-adjlistw.firstarc;while(p!=NULL)if(visitedp-adjvex=0)printf(%d,p-adjvex);visitedp-adjvex=1;-word.zl.for(i=0;in;i+)p=G-adjlisti.firstarc;printf(%d:,i);while(p!=NULL)printf(%d,p-adjvex);p=p-nextarc;printf

6、(n);Arode*p;visited v=1;printf(%d,v);p=G-adjlistv.firstarc;while(p!=NULL)if(visitedp-adjvex=0)dfs(G,p-adjvex);p=p-nextarc;.-rear=(rear+1)%6;queuerear=p-adjvex;p=p-nextarc;printf(n);int main()bfs(G,0);-word.zl.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,

7、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+)G=(ALGraph*)malloc(sizeof(ALGraph);mattolist(g,G);dispadj(G);for(j=0;jg.n;j+)printf(%d,g.aij);printf(n);printf(-邻接矩阵-n);printf(-邻接表-n);dfs(G,0);printf(n);printf(-从 0 开场的深度优先遍历-n);printf(n);return 0;printf(-从 0 开场的广度优先遍历-

8、n);.-word.zl.-6实验分析与体会通过此次实验，使我更加深刻的明白了图在计算机中是如何存储的，图在计算机中的存储有两种，一种是邻接矩阵存储方式，这种方式我们主要是运用到了二维数组的特性，通过二维数组来明确表现出节点与节点的位置关系，第二种就是我们说的邻接表存储构造，这种构造主要是运用到了指针来实现。而当我们在进展图的遍历时，首先要选择一个起始点，上面我们选择的是 0 为起始点，当我们在进展深度优先遍历时，可以用递归的思想，而在广度优先遍历时，不能用递归，这个要注意。在这次的实验中，通过对图的操作，使我对数组和指针都有了更加深刻地认识，我认为我们要多打代码，因为这样我们才能够更全面的理解每一个指令的意思，同时我们也应该要将代码分成一个更小的指令的看，这样我们对程序将有更好地提高，更大的认识。实验日期：2016 年 11 月 17 日-word.zl.-教师评语签名：年月日-word.zl.