用邻接表遍历图实验报告.doc

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

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

2、端删除；2.算法设计关键算法与分析①　边表结点与顶点表结点的建立②　建立一个有n个顶点e条边的有向图..页脚..①　有向图的深度优先遍历②　有向图的广度优先遍历..页脚..①　求某个顶点的度一、运行与测试正确的运行结果二、总结与心得运用邻接表来实现有向图的深度和广度优先遍历，在建立邻接表的时候，我发现运用结点能够更好地表示点与点之间的关系，在邻接表中，我们运用了顶点表结点和边表结点。无论是以前学习的单链表，双链表，树，二叉树，里面的点都是运用结点来实现数据之间的关系三、附录（程序完整代码）ALGraph.h#ifndefALGraph_H//定义头文件#

3、defineALGraph_HconstintMaxSize=10;//图的最大顶点数structArcNode//定义边表结点..页脚..{intadjvex;//存放该顶点的邻接结点在顶点表中的下标ArcNode*next;//该顶点的其他邻接结点(边表结构)-指向边表中的下一个结点};templatestructVertexNode//定义顶点表结点{DataTypevertex;//存放顶点信息ArcNode*firstedge;//存放顶点的第一个邻接结点（边表结构）};template

4、>classALGraph{public:ALGraph(DataTypea[],intn,inte);//构造函数，建立一个有n个顶点e条边的图~ALGraph();//析构函数，释放邻接表中各边表结点的存储空间voidDFSTraverse(intv);//深度优先遍历图voidBFSTraverse(intv);//广度优先遍历图intDu(intx);//求第x个顶点的度private:VertexNodeadjlist[MaxSize];..页脚..//存放顶点表的数组intvertexNum,arcNum;//图的顶点数和

5、边数};#endifALGraph.cpp#includeusingnamespacestd;#include"ALGraph.h"//引入头文件templateALGraph::ALGraph(DataTypea[],intn,inte){ArcNode*s;inti,j,k;vertexNum=n;arcNum=e;for(i=0;i

6、NULL;}for(k=0;k>i>>j;//输入边所依附的两个顶点的编号..页脚..s=newArcNode;s->adjvex=j;//生成一个边表结点ss->next=adjlist[i].firstedge;//将结点s插入到第i个边表的表头adjlist[i].firstedge=s;}}templateALGraph::~ALGraph(){ArcNode*p;for(inti=0;i

7、xNum;i++){p=adjlist[i].firstedge;while(p!=NULL)//循环删除{adjlist[i].firstedge=p->next;deletep;//释放结点空间p=adjlist[i].firstedge;}}}templatevoidALGraph::DFSTraverse(intv){ArcNode*p;..页脚..intj;cout<

8、点v的边表while(p!=NULL)//依次搜索顶点v的邻接点j{j=p->a