图的邻接矩阵实验报告

数据结构与算法实验院别：计算机科学与信息工程学院年级专业：2014级空间信息与数字技术姓名：杨哲庆学号：1420012138评语和成绩:2015年12月实验7图的邻接矩阵实验7.1图的遍历7.1.1实验的主要内容和目的①掌握图的逻辑结构；②掌握图的邻接矩阵存储结构；③验证图的邻接矩阵存储及其遍历操作的实现。7.1.2代码MGraph.h(MGraph类的声明)#if!defined(AFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_)#defineAFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_#if_MSC_VER1000#pragmaonce#endif//_MSC_VER1000constintMax=20;//图中最多顶点的个数templateclassTclassMGraph{public:MGraph();voidDFS(intk);//深度优先遍历（递归算法）voidBFS(intk);//广度优先遍历voidDFS_v2(intk);//深度优先遍历（非递归算法）private:Tvertex[Max];//存放图中顶点信息的数组intarc[Max][Max];//邻接矩阵数组intvertexNum,arcNum;//顶点数和边数};#endifMGraph.cpp(MGraph类的实现)#includeiostreamusingnamespacestd;#includeMGraph.htemplateclassTMGraphT::MGraph(){inti,j,k;cout请输入顶点的个数vertexNum：;cinvertexNum;cout请输入边的条数arcNum：;cinarcNum;for(i=0;ivertexNum;i++){cout请输入第i+1个顶点的信息\t;cinvertex[i];}for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)//初始化图的邻接矩阵arc[i][j]=0;for(k=0;karcNum;k++)//存储图的边信息{cout请输入边的两个顶点的序号：;cinij;arc[i][j]=1;arc[j][i]=1;}}templateclassTvoidMGraphT::DFS(intk)//从顶点k出发进行广度优先遍历{coutvertex[k];//输出访问的顶点visited[k]=1;//visited数组访问标记置为1表示已经访问for(intj=0;jvertexNum;j++)//循环调用自身（递归算法）if((arc[k][j]==1)&&(!visited[j]))DFS(j);}templateclassTvoidMGraphT::BFS(intk)//从顶点k出发进行广度优先遍历{intqueue[Max];//定义个队列queueintfront=-1,rear=-1;//front和rear分别为头指针和尾指针coutvertex[k];visited[k]=1;//将其标记为已访问queue[++rear]=k;while(front!=rear){k=queue[++front];//将队头元素出队并且送到k中for(intj=0;jvertexNum;j++)if((arc[k][j]==1)&&(!visited[j])){coutvertex[j];visited[j]=1;queue[++rear]=j;}}}templateclassTvoidMGraphT::DFS_v2(intk){inttop=0;int*s=newint[vertexNum];//初始化一个s栈coutvertex[k];visited[k]=1;//为k置为已访问标志top++;s[top]=k;while(top!=0){intv=s[top];for(inti=0;ivertexNum;i++)if(arc[v][i])//若v,j边存在if(!visited[i])//若顶点i未被访问过{coutvertex[i];//输出该顶点visited[i]=1;//为i置为已访问标志top++;s[top]=i;//i进栈break;//跳出循环}if(i==vertexNum)//若v已无未访问的出点，则将其退栈top--;}}test.cpp(主函数测试文件)#includeiostreamusingnamespacestd;#includeMGraph.cppintvisited[Max]={0};intmain(){MGraphcharg;for(inti=0;iMax;i++)visited[i]=0;charxunhuan('Y');while(xunhuan=='Y'){cout深度优先遍历（递归算法）的序列是：;g.DFS(0);coutendl;cout继续进行深度优先遍历（递归算法）吗？（Y/N）endl;cinxunhuan;if(xunhuan=='N')break;}for(i=0;iMax;i++)visited[i]=0;xunhuan='Y';while(xunhuan=='Y'){cout深度优先遍历（非递归算法）的序列是：;g.DFS_v2(0);coutendl;cout继续进行深度优先遍历（递归算法）吗？（Y/N）endl;cinxunhuan;if(xunhuan=='N')break;}for(i=0;iMax;i++)visited[i]=0;xunhuan='Y';while(xunhuan=='Y'){cout广度优先遍历的序列是：;g.BFS(0);coutendl;cout继续进行深度优先遍历（递归算法）吗？（Y/N）endl;cinxunhuan;if(xunhuan=='N')break;}return0;}7.1.3总结（1）实验过程中遇到的三个有意义的错误。a.运行程序出现如下错误，如图1-1。错误原因是重复定义。图1-1找到出错代码所在位置，如图1-2所示。图1-2将“intvisited[Max]={0}”转移至test.cpp文件下。如图1-3所示。错误消失。图1-3b.出现如图2-1所示错误。图2-1找到出错代码所在位置，错误代码为“ints[vertexNum]”，如图2-2。图2-2将代码“ints[vertexNum]”改为“int*s=newint[vertexNum]”，如图2-3，错误消失。错误原因在于vertexNum是变量，而定义数组时，数组的大小要由常量确定。如果要由变量来确定，则需要通过动态分配。图2-3c.没有错误提示，但是运行程序后出现如图3-1所示的无限输出“ABABAB…”并且程序奔溃。图3-1通过设置断点进行调试，找到了出错代码所在位置。错误代码为“if(arc[v][i])”，如图3-2。错误原因在于，有些已被访问过的顶点再次被访问，而这个循环中没有一个限制的条件（缺少个if判断语句）。图3-2在“if(arc[v][i])”语句下面再加入“if(!visited[i])”进行判断，如果顶点被访问过，则!visited[i]的值为0如图3-3所示。图3-3（2）实验过程使用的主要知识点。a.建立无向图的邻接矩阵存储；b.对建立的无向图，进行深度优先遍历用到递归和非递归算法；c.对建立的无向图，进行广度优先遍历；（3）实验中遇到的不理解或体会比较深的问题。a.不理解图1-1所示错误，为什么“intvisited[Max]={0}”不能放在MGraph.cpp中。当“intvisited[Max]={0}”放在MGraph.cpp中，则编译器会提示visited数组已编译。唯有放在test.cpp中错误提示才会消失。b.在构思深度优先遍历的非递归算法时，不知道该如何用像递归算法那样，当访问到一个符合条件的值时，就再次调用此函数，同时将该值传给函数。为此，考虑到了可以利用栈模型，将此时正在访问的顶点的序号传入栈中，在下次while循环的时候，取出栈顶元素，以该元素为起点继续进行相同操作，直至访问全部的顶点为止。c.设计了访问全部顶点的非递归算法，但是一开始不知道如何结束函数中的while循环，觉得要设置个判断条件来判断是否全部顶点都被访问，想的太复杂了。后来想起每访问一个顶点s栈中都会多出一个元素。栈中的元素个数就是图的顶点个数，只要利用top=0就可以跳出循环，所以在while循环的末尾加上了“if(i==vertexNum)top--”类似与递归算法中，函数值从最底层一步一步回到最初一层。