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

《数据结构（C++版）》实验报告班 级 1405 学 号 姓 名 徐妍题 目 用邻接表遍历图指导教师 王江涛计算机科学与技术学院2023年12月12日实验题目：用邻接表遍历图一、 实验目的：1. 掌握图的逻辑结构2. 掌握图的邻接表存储结构3. 验证图的邻接表存储及其深度和广度优先遍历操作的实现二、 实验内容：1. 建立一个有向图的邻接表存储结构2. 对建立的有向图，进行深度优先遍历3. 对建立的有向图，进行广度优先遍历三、 设计与编码1. 本实验用到的理论知识①　 边表结点与顶点表结点的建立（类似单链表中的结点）；②　 队列的特点：只能在一端插入，另一端删除；2. 算法设计 关键算法与分析①　 边表结点与顶点表结点的建立②　 建立一个有n个顶点e条边的有向图③　 有向图的深度优先遍历④　 有向图的广度优先遍历⑤　 求某个顶点的度四、 运营与测试对的的运营结果五、 总结与心得运用邻接表来实现有向图的深度和广度优先遍历，在建立邻接表的时候，我发现运用结点可以更好地表达点与点之间的关系，在邻接表中，我们运用了顶点表结点和边表结点无论是以前学习的单链表，双链表，树，二叉树，里面的点都是运用结点来实现数据之间的关系六、 附录（程序完整代码）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 ALGraph{public: 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 adjlist[MaxSize]; //存放顶点表的数组 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++) //输入顶点信息，初始化顶点表 { adjlist[i].vertex = a[i]; adjlist[i].firstedge = NULL; } for (k = 0; k < arcNum; k++) //依次输入每一条边 { cout<<"请输入边的两个顶点的序号："; cin >> i >> j; //输入边所依附的两个顶点的编号 s = new ArcNode; s->adjvex = j; //生成一个边表结点s s->next = adjlist[i].firstedge; //将结点s插入到第i个边表的表头 adjlist[i].firstedge = s; }}template ALGraph::~ALGraph( ){ ArcNode *p; for(int i=0; inext; delete p; //释放结点空间 p=adjlist[i].firstedge; } }}template void ALGraph::DFSTraverse(int v){ ArcNode *p; int j; cout<adjvex; if (visited[j] == 0) DFSTraverse(j); p = p->next; }} template void ALGraph::BFSTraverse(int v){ int front = -1, rear = -1;//初始化队列, 假设队列采用顺序存储且不会发生溢出 int Q[MaxSize]; ArcNode *p; cout<adjvex; if (visited[j] == 0) { cout<next; } }}template int ALGraph::Du(int x)//求第x个顶点的度 { int count=0; ArcNode *p; p=adjlist[x].firstedge; while(p!=NULL) { count++; p=p->next; } return count; }ALGraphmain.cpp#include using namespace std;#include "ALGraph.cpp"int visited[MaxSize] = {0};void main(){ char ch[ ]={'A','B','C','D','E'}; int i; ALGraph ALG(ch, 5, 6); for (i = 0; i < MaxSize; i++) visited[i] = 0; cout<<"深度优先遍历序列是："; ALG.DFSTraverse(0); cout<>x; cout<<"第"<