用邻接表遍历图实验报告

《用邻接表遍历图实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构（C++版）》实验报告班级1405学号211415034姓名徐妍题目用邻接表遍历指导教师王江涛计算机科学与技术学院2015年1212实验题目：用邻接表遍历、实验目的:1.掌握图的逻辑结构2.掌握图的邻接表存储结构3.验证图的邻接表存储及其深度和广度优先遍历操作的实现、实验内容:1.建立一个有向图的邻接表存储结构2.对建立的有向图，进行深度优先遍历3.对建立的有向图，进行广度优先遍历三、设计与编码1.本实验用到的理论知识①边表结点与顶点表结点的建立（类似单链表中的结点）；②队列的特点：只能在一

2、端插入，另一端删除；2.算法设计关键算法与分析①边表结点与顶点表结点的建立estructArcNode//定义边表结点intadjvex;//存放该顶点的邻接结点在顶点表中的下标ArcNode*next;//该顶点的其他邻接结点（边表结构）-指向边表中的下一个结点};znTtemplate〈classDataType>tstructVertexNode//定义顶点表结点DataTypevertex;//存放顶点信息ArcNode*firstedge;//存放顶点的第一个邻接结点（边表结构）②建立一个有

3、n个顶点e条边的有向［templateFALGraph;:ALGraph(DataTypea[]rintn,inte)IArcNode*s:inti,jrk;vertexNum=n;arcNum=e;for(i=0;i

4、c请输入边的两个顶点的序号.11-•Vcin»i»j;//输入边所依附的两个顶点的编号s=newArcNode;s->adjvex=j;//生成一个边表结点ss->next=adj1ist[i].firstedge;//将结点S插入到第i个边表的表头adj1ist[i].firstedge=s;}}①有向图的深度优先遍历template〈classDataType>戸voidALGraph::DFSTraverse(intv){ArcNode*p;intj;cout〈〈adjIis

5、t[v]，vertex;visited[v]=1;p=adjIist[v].firstedge;//工作指针p指向顶点v的边表while(p!=NULL)//依次搜索顶点v的邻接点j{j=p->adjvex;if(visited[j]==0)DFSTraverse(j);p-p_〉next;I}②有向图的广度优先遍历tempIate::BFSTraverse(intv){intfront=-1frear=-1;//初始化队列，假

6、设队列采用顺序存储且不会发生溢出intQ[MaxSize];ArcNode*p;cout«adjIist[v].vertex;visited[v]=1;0[++rear]=v;//被访问顶点入队while(front!=rear)//当队列非空时{v=0[++front];p=adjIist[v].firstedge;//工作指针p指向顶点v的边表while(p!=NULL)tint」=p->adjvex;if(visited[j]=0){cout«adjIist[j].vertex;visited[

7、j]=1;Q[++rear]=j;}p=p-〉next;①求某个顶点的度template0intALGraph〈DataType>::Du(intx)./求第x个顶点的度{intcount=0;ArcNode*p;p=adjIist[x].firstedge;while(p!=NULL){count++;p=p->next;}returncount;}四、运行与测试正确的运行结果请输入边的两个顶点的序号：01请输入边的两个顶点的序号：02请输入边的两个顶点的序号：04请输

8、入边的两个顶点的序号：13请输入边的两个顶点的序号：24请输入边的两个顶点的序号：34深度优先遍历序列是：AECBD广度优先遍历序列是：AECBD请输入你想要知道度的顶点的序号0第0个顶点的度为3请按任意键继续...五、总结与心得运用邻接表来实现有向图的深度和广度优先遍历，在建立邻接表的时候，我发现运用结点能够更好地表示点与点之间的关系，在邻接表中，我们运用了顶点表结点和边表结点。无论是以前学习的单链表，双链表，树，二叉树，里面的点都是运用结点来实现数据