图的邻接矩阵实验报告

1、 数据结构与算法实验院 别：计算机科学与信息工程学院年级专业：2014级空间信息与数字技术姓 名：杨哲庆学 号：评语和成绩: 2015 年 12月 实验7 图的邻接矩阵 实验7.1图的遍历7.1.1实验的主要内容和目的 掌握图的逻辑结构； 掌握图的邻接矩阵存储结构； 验证图的邻接矩阵存储及其遍历操作的实现。7.1.2代码MGraph.h (MGraph类的声明)#if !defined(AFX_MGRAPH_H_FDC762FA_D8BE_473C_B917_CAE3F_INCLUDED_)#define AFX_MGRAPH_H_FDC762FA_D8BE_473C_B917_CAE3F_I

2、NCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000const int Max=20; /图中最多顶点的个数templateclass MGraph public:MGraph(); void DFS(int k); /深度优先遍历（递归算法）void BFS(int k); /广度优先遍历void DFS_v2(int k); /深度优先遍历（非递归算法）private:T vertexMax; /存放图中顶点信息的数组int arcMaxMax; /邻接矩阵数组int vertexNum,arcNum; /顶点数和边数;#e

3、ndif MGraph.cpp (MGraph类的实现)#includeusing namespace std;#include MGraph.htemplateMGraph:MGraph()int i,j,k;cout请输入顶点的个数vertexNum：vertexNum;cout请输入边的条数arcNum：arcNum;for(i=0;ivertexNum;i+)cout请输入第i+1个顶点的信息vertexi;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)/初始化图的邻接矩阵arcij=0;for(k=0;karcNum;k+) /存储图的边信息

4、coutij;arcij=1;arcji=1;templatevoid MGraph:DFS(int k) /从顶点k出发进行广度优先遍历coutvertexk ; /输出访问的顶点visitedk=1; /visited数组访问标记置为1表示已经访问for(int j=0;jvertexNum;j+) /循环调用自身（递归算法）if( (arckj=1) & (!visitedj) ) DFS(j);templatevoid MGraph:BFS(int k) /从顶点k出发进行广度优先遍历int queueMax; /定义个队列queueint front=-1,rear=-1; /fro

5、nt和rear分别为头指针和尾指针coutvertexk ; visitedk=1; /将其标记为已访问queue+rear=k;while(front!=rear) k=queue+front; /将队头元素出队并且送到k中for(int j=0;jvertexNum;j+)if( (arckj=1) & (!visitedj) )coutvertexj ;visitedj=1;queue+rear=j;templatevoid MGraph:DFS_v2(int k)int top=0;int *s=new intvertexNum; /初始化一个s栈coutvertexk ;visite

6、dk=1; /为k置为已访问标志top+;stop=k;while(top!=0)int v=stop;for(int i=0;ivertexNum;i+)if(arcvi) /若边存在if(!visitedi) /若顶点i未被访问过coutvertexi ; /输出该顶点visitedi=1; /为i置为已访问标志top+;stop=i; /i进栈break; /跳出循环if(i=vertexNum) /若v已无未访问的出点，则将其退栈top-;test.cpp(主函数测试文件)#includeusing namespace std;#includeMGraph.cppint visited

7、Max=0;int main()MGraph g;for(int i=0;iMax;i+)visitedi=0;char xunhuan(Y);while(xunhuan=Y)cout深度优先遍历（递归算法）的序列是：;g.DFS(0);coutendl;cout继续进行深度优先遍历（递归算法）吗？（Y/N）xunhuan;if(xunhuan=N)break;for(i=0;iMax;i+)visitedi=0;xunhuan=Y;while(xunhuan=Y)cout深度优先遍历（非递归算法）的序列是：;g.DFS_v2(0);coutendl;cout继续进行深度优先遍历（递归算法）吗

8、？（Y/N）xunhuan;if(xunhuan=N)break;for(i=0;iMax;i+)visitedi=0;xunhuan=Y;while(xunhuan=Y)cout广度优先遍历的序列是：;g.BFS(0);coutendl;cout继续进行深度优先遍历（递归算法）吗？（Y/N）xunhuan;if(xunhuan=N)break;return 0;7.1.3总结 （1）实验过程中遇到的三个有意义的错误。a. 运行程序出现如下错误，如图1-1。错误原因是重复定义。图1-1找到出错代码所在位置，如图1-2所示。图1-2将“int visitedMax=0”转移至test.cpp文件

9、下。如图1-3所示。错误消失。图1-3b. 出现如图2-1所示错误。图2-1找到出错代码所在位置，错误代码为“int svertexNum”，如图2-2。图2-2将代码“int svertexNum”改为“int *s=new intvertexNum”，如图2-3，错误消失。错误原因在于vertexNum是变量，而定义数组时，数组的大小要由常量确定。如果要由变量来确定，则需要通过动态分配。图2-3c. 没有错误提示，但是运行程序后出现如图3-1所示的无限输出“ABABAB”并且程序奔溃。图3-1通过设置断点进行调试，找到了出错代码所在位置。错误代码为“if(arcvi)”，如图3-2。错误原

10、因在于，有些已被访问过的顶点再次被访问，而这个循环中没有一个限制的条件（缺少个if判断语句）。图3-2在“if(arcvi)”语句下面再加入“if(!visitedi)”进行判断，如果顶点被访问过，则!visitedi的值为0如图3-3所示。图3-3（2）实验过程使用的主要知识点。a. 建立无向图的邻接矩阵存储；b. 对建立的无向图，进行深度优先遍历用到递归和非递归算法；c. 对建立的无向图，进行广度优先遍历；（3）实验中遇到的不理解或体会比较深的问题。a. 不理解图1-1所示错误，为什么“int visitedMax=0”不能放在MGraph.cpp中。当“int visitedMax=0”放在MGraph.cpp中，则编译器会提示visited数组已编译。唯有放在test.cpp中错误提示才会消失。b. 在构思深度优先遍历的非递归算法时，不知道该如何用像递归算法那样，当访问到一个符合条件的值时，就再次调用此函数，同时将该值传给函数。为此，考虑到了可以利用栈模型，将此时正在访问的顶点的序号传入栈中，在下次while循环的时候，取出栈顶元素，以该元素为起点继续进行相同操作，直至访问全部的顶点为止。c. 设计了访问全部顶点的非递归算法，但是一开始不