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

第 10 页 共 10 页 数据结构（C+版）实验报告班 级1405 学 号 211415034姓 名徐妍题 目 用邻接表遍历图指导教师 王江涛计算机科学与技术学院2015年12月12日实验题目：用邻接表遍历图1、 实验目的：1. 掌握图的逻辑结构2. 掌握图的邻接表存储结构3. 验证图的邻接表存储及其深度和广度优先遍历操作的实现2、 实验内容：1. 建立一个有向图的邻接表存储结构2. 对建立的有向图，进行深度优先遍历3. 对建立的有向图，进行广度优先遍历3、 设计与编码1. 本实验用到的理论知识1 边表结点与顶点表结点的建立（类似单链表中的结点）；2 队列的特点：只能在一端插入，另一端删除；2. 算法设计 关键算法与分析1 边表结点与顶点表结点的建立2 建立一个有n个顶点e条边的有向图3 有向图的深度优先遍历4 有向图的广度优先遍历5 求某个顶点的度4、 运行与测试正确的运行结果5、 总结与心得运用邻接表来实现有向图的深度和广度优先遍历，在建立邻接表的时候，我发现运用结点能够更好地表示点与点之间的关系，在邻接表中，我们运用了顶点表结点和边表结点。无论是以前学习的单链表，双链表，树，二叉树，里面的点都是运用结点来实现数据之间的关系6、 附录（程序完整代码）ALGraph.h#ifndef ALGraph_H /定义头文件#define ALGraph_Hconst int MaxSize=10; /图的最大顶点数struct ArcNode /定义边表结点 int adjvex; /存放该顶点的邻接结点在顶点表中的下标 ArcNode *next;/该顶点的其他邻接结点(边表结构)-指向边表中的下一个结点;template struct VertexNode /定义顶点表结点 DataType vertex;/存放顶点信息 ArcNode *firstedge;/存放顶点的第一个邻接结点（边表结构）;template class ALGraphpublic: ALGraph(DataType a , int n, int e); /构造函数，建立一个有n个顶点e条边的图 ALGraph( ); /析构函数，释放邻接表中各边表结点的存储空间 void DFSTraverse(int v); /深度优先遍历图 void BFSTraverse(int v); /广度优先遍历图 int Du(int x);/求第x个顶点的度private: VertexNode adjlistMaxSize; /存放顶点表的数组 int vertexNum, arcNum; /图的顶点数和边数;#endifALGraph.cpp#include using namespace std;#include ALGraph.h /引入头文件template ALGraph:ALGraph(DataType a , int n, int e)ArcNode *s;int i, j, k;vertexNum = n; arcNum = e;for (i = 0; i vertexNum; i+) /输入顶点信息，初始化顶点表 adjlisti.vertex = ai;adjlisti.firstedge = NULL; for (k = 0; k arcNum; k+) /依次输入每一条边 cout i j; /输入边所依附的两个顶点的编号s = new ArcNode; s-adjvex = j; /生成一个边表结点ss-next = adjlisti.firstedge; /将结点s插入到第i个边表的表头adjlisti.firstedge = s;template ALGraph:ALGraph( )ArcNode *p;for(int i=0; inext;delete p; /释放结点空间p=adjlisti.firstedge;template void ALGraph:DFSTraverse(int v)ArcNode *p; int j;coutadjvex;if (visitedj = 0)DFSTraverse(j);p = p-next; template void ALGraph:BFSTraverse(int v)int front = -1, rear = -1;/初始化队列, 假设队列采用顺序存储且不会发生溢出int QMaxSize; ArcNode *p;coutadjvex;if (visitedj = 0) coutnext;template int ALGraph:Du(int x)/求第x个顶点的度 int count=0; ArcNode *p; p=adjlistx.firstedge; while(p!=NULL) count+; p=p-next; return count; ALGraphmain.cpp#include using namespace std;#include ALGraph.cppint visitedMaxSize = 0;void main()char ch =A,B,C,D,E;int i;ALGraph ALG(ch, 5, 6);for (i = 0; i MaxSize; i+)visitedi = 0;cout深度优先遍历序列是：;ALG.DFSTraverse(0);coutendl; for (i = 0