实验八邻接矩阵验证及邻接表的验证.docVIP

江西理工大学软件学院 计算机类课程实验报告 课程名称： 数据结构（C++） 实验名称： 邻接矩及邻接表的验证 班 级： 14软件土木4班 姓 名： 张凌云 学 号： 江西理工大学软件学院实验八 实验名称 邻接矩阵及邻接表的验证 实验日期 2015-12-22 实验成绩 实验目的、要求及内容 （给出本次实验所涉及并要求掌握的知识点及实验内容具体描述） 实验目的： （1）：掌握图的逻辑结构； （2）：掌握图的邻接矩阵和邻接表存储结构； （3）：验证图的邻接矩阵和邻接表存储及遍历操作的实现； 二、实验内容： 建立无向图的邻接矩阵存储； 建立一个有向图的邻接表存储结构； 对建立的无向图和无向图，进行深度优先遍历； 对建立的无向图和有向图，进行深度优先遍历 上机调试程序，按规定格式输入数据； 上机调试，程序分析； 编写程序 实验环境 （列出本次实验所使用的平台和相关软件） 3323机房 OS：Win8 C++环境：1、vs2010 算 法 描 述 及 实 验 步 骤 邻接矩阵 过程 深度优先遍历算法在邻接矩阵存储结构下实现 采用度优先遍历算法在邻接矩阵存储结构下实现 结果 程序运行结果如下图 邻接表 过程 采用头插法深度优先遍历算法在邻接矩阵存储结构下 实现 采用头插法度优先遍历算法在邻接矩阵存储结构下实现 ： 结果 程序运行结果如下图 邻接矩阵 邻接表 总结 附录 邻接矩阵的实现 //MGraph.h #ifndef MGraph_H #define MGraph_H const int maxsize = 100; templateclass DataType class MGraph { public : MGraph(DataType a[], int n, int e); ~MGraph(){} void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[maxsize]; int arc[maxsize][maxsize]; int vertexNum, arcNum; }; #endif //MGraph.cpp #include iostream using namespace std; #include MGraph.h template class DataType MGraphDataType::MGraph(DataType a[], int n, int e) { int i, j; vertexNum = n; arcNum = e; for (i = 0; i vertexNum; i++) vertex[i] = a[i]; for (i = 0; i vertexNum; i++) for (j = 0; j vertexNum; j++) arc[i][j] = 0; for (int k = 0; k arcNum; k++) { cout 请输入边的两个顶点的序号：; cin i; cin j; arc[i][j] = 1; arc[j][i] = 1; } } template class DataType void MGraphDataType::DFSTraverse(int v) { cout vertex[v]; visited[v] = 1; for (int j = 0; j vertexNum; j++) if (arc[v][j] == 1 visited[j] == 0) DFSTraverse(j); } template class DataType void MGraphDataType::BFSTraverse(int v) { int Q[maxsize]; int front = -1, rear = -1; cout vertex[v]; visited[v] = 1; Q[++rear] = v; while (front != rear) { v = Q[++front]; for (int j = 0; j vertexNum; j++) if (arc[v][j] == 1 visited[j] == 0) { cout ver