图结构试验实验报告

1、附件（四）深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 图结构实验 学院： 计算机与软件学院 专业： 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务处制一、实验目的与完成说明：1. 简单介绍本实验的主要目的2. 说明你自己在本次实验中完成了第几项要求（必填）Contest1620 - DS实验08-图遍历【11.12】Problem A: DS图遍历-深度优先搜索Description主要目的：给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始（完成）注意：图n个顶点编号从0到n-1Input第一行输入t，表示有t个测试实

2、例（完成）第二行输入n，表示第1个图有n个结点（完成）第三行起，每行输入邻接矩阵的一行，以此类推输入n行（完成）第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开（完成）以此类推输入下一个示例（完成）Output每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开（完成）Problem B: DS图遍历-广度优先搜索Description给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始（完成）注意：图n个顶点编号从0到n-1Input第一行输入t，表示有t个测试实例（完成）第二行输入n，表示第1个图有n个结点（完成）第三行起，每行输入邻接矩阵的一行，以此类推输入n

3、行（完成）第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开（完成）以此类推输入下一个示例Output每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开（完成）Contest1638 - DS实验09-最短路径【11.19】Problem A: DS图应用-最短路径Description给出一个图的邻接矩阵，再给出指定顶点v0，求顶点v0到其他顶点的最短路径（完成）Input第一行输入t，表示有t个测试实例（完成）第二行输入n，表示第1个图有n个结点（完成）第三行起，每行输入邻接矩阵的一行，以此类推输入n行（完成）第i个结点与其他结点如果相连则为1，无连接则为0，数据之

4、间用空格隔开第四行输入v0，表示求v0到其他顶点的最短路径距离（完成）以此类推输入下一个示例Output每行输出v0到某个顶点的最短距离和最短路径（完成）每行格式：v0编号-其他顶点编号-最短路径，具体请参考示范数据（完成）二、主要思路与方法：1. 对于本次实验，说明你认为最重要的函数、算法或知识点，并谈谈你对它们的理解Contest1620 - DS实验08-图遍历【11.12】Problem A: DS图遍历-深度优先搜索043210312从0开始连续获取邻接结点，然后逐个遍历并设Visit为true避免重复遍历04321Problem B: DS图遍历-广度优先搜索0312首先将该顶点的

5、邻接顶点全部入队，然后挨个读取，在读取的过程中继续将邻接矩阵入队，并把已经读取过的顶点全被设为true。Contest1638 - DS实验09-最短路径【11.19】120341527515Problem A: DS图应用-最短路径 输入mx矩阵Mx012340050715100500200001300200400000初始化并赋值Matrix的矩阵Matrix01234057151521324初始化并赋值path的矩阵Path012340-1-1-1-1-1101-1-1-12-1-1-1-1-130-1-13-140-1-1-14初始化并赋值dist数组Dist012345715初始并赋

6、值len数组Len0123455555 i=1的时候;min=9999;v=1;min=5;final1=true;可以访问。Dist2=5+ Matrix12=10;2=1;Path数组改变Path0123450-1-1-1-1-1101-1-1-1201-1-1-1230-1-13-140-1-1-14Dist数组改变Dist01234510715v=3;min=7;final3=true;可以访问。Dist2=7+ Matrix32=9;2=3;Path数组改变Path0123450-1-1-1-1-1101-1-1-120-1-13-1230-1-13-140-1-1-14Dist数组

7、改变Dist0123459715v=2;min=9;final2=true;可以访问。Dist4=9+Matrix24=10;4=2;Path数组改变Path01234560-1-1-1-1-1101-1-1-120-1-13-1230-1-13-140-1-13-124Dist数组改变Dist0123459710三实验程序或内容：1. 针对每一项实验要求，给出编写的代码，2. 可以粘贴全部代码，或者可以只粘贴重要的代码（为了节省纸张），但代码必须完整，至少是完整的函数。3. 代码符合以下要求，评分更高：a. 排版整齐，可读性高b. 代码有注释，越详细越清晰越好Contest1620 - DS

8、实验08-图遍历【11.12】Problem A: DS图遍历-深度优先搜索#include using namespace std; const int MaxLen=20; class Map private: bool VisitMaxLen; int MatrixMaxLenMaxLen; int Vexnum; void DFS(int v); public: void SetMatrix(int vnum,int mxMaxLenMaxLen); void DFSTraverse(); ; /设置邻接矩阵 void Map:SetMatrix(int vnum,int mxMaxL

9、enMaxLen) int i,j; Vexnum=vnum; for(i=-1;+iMaxLen;) for(j=-1;+jMaxLen;) Matrixij=0; for(i=-1;+iVexnum;) for(j=-1;+jVexnum;) Matrixij=mxij; void Map:DFSTraverse() int v; /将所有的Visit赋值为false for(v=-1;+vVexnum;) Visitv=false; /开始逐个遍历未访问结点 for(v=-1;+vVexnum;) if(!Visitv) DFS(v); /if /for coutendl; void M

10、ap:DFS(int v) int w,i,k; Visitv=true; /输出访问的结点 coutv ; /初始化AdjVex int *AdjVex=new intVexnum; for(i=-1;+iVexnum;) AdjVexi=-1;/开始遍历这个顶点能到达的邻接顶点 k=0; for(i=-1;+it; while(t-) cinn; int mx2020; for(i=-1;+in;) for(j=-1;+jmxij; m.SetMatrix(n,mx); m.DFSTraverse(); return 0; Problem B: DS图遍历-广度优先搜索#include #

11、include using namespace std; const int MaxLen=20; class Map private: bool VisitMaxLen; int MatrixMaxLenMaxLen; int Vexnum; void DFS(int v); public: void SetMatrix(int vnum,int mxMaxLenMaxLen); void DFSTraverse(); void BFSTraverse(); void BFS(int v); ; /设置邻接矩阵 void Map:SetMatrix(int vnum,int mxMaxLen

12、MaxLen) int i,j; Vexnum=vnum; for(i=-1;+iMaxLen;) for(j=-1;+jMaxLen;) Matrixij=0; for(i=-1;+iVexnum;) for(j=-1;+jVexnum;) Matrixij=mxij; void Map:DFSTraverse() int v; for(v=-1;+vVexnum;) Visitv=false; for(v=-1;+vVexnum;) if(!Visitv) DFS(v); /if coutendl; void Map:DFS(int v) int w,i,k; Visitv=true; c

13、outv ; int *AdjVex=new intVexnum; for(i=-1;+iVexnum;) AdjVexi=-1; k=0; for(i=-1;+iVexnum;) if(Matrixvi) AdjVexk+=i; /if /for i=0; for(;w=AdjVexi+,w!=-1;) if(!Visitw) DFS(w); /if /for deleteAdjVex; void Map:BFSTraverse() BFS(0); void Map:BFS(int v) int w,u; int i,k; int *AdjVex=new intVexnum; queueQ;

14、 for(i=-1;+iVexnum;) Visiti=false; /for for(i=-1;+iVexnum;) AdjVexi=-1; for(v=-1;+vVexnum;) if(!Visitv) Visitv=true; coutv ; Q.push(v); while(!Q.empty() u=Q.front(); Q.pop(); k=0; for(i=-1;+iVexnum;) if(Matrixui) AdjVexk+=i; /if /for i=0; for(;w=AdjVexi+,w!=-1;) if(!Visitw) Visitw=true; coutw ; Q.pu

15、sh(w); /if /for /while /if /for coutt; while(t-) cinn; int mx2020; for(i=-1;+in;) for(j=-1;+jmxij; m.SetMatrix(n,mx); m.BFSTraverse(); return 0; Contest1638 - DS实验09-最短路径【11.19】Problem A: DS图应用-最短路径#include using namespace std; const int MaxLen=20; const int MaxDist=9999; class Map private: int Matr

16、ixMaxLenMaxLen; int Vexnum; public: void SetMatrix(int vnum,int mxMaxLenMaxLen); void ShortestPath_DIJ(int v0); ; void Map:SetMatrix(int vnum,int mxMaxLenMaxLen) /给矩阵赋值 int i,j; Vexnum=vnum; /定点数量赋值/先给所有的矩阵初始化为9999 for(i=-1;+iMaxLen;) for(j=-1;+jMaxLen;) Matrixij=MaxDist; /把mx矩阵的内容赋给Matrix for(i=-1;

17、+iVexnum;) for(j=-1;+jVexnum;) if(mxij) Matrixij=mxij; void Map:ShortestPath_DIJ(int v0) int i,j,v,w,min; int *dist=new intVexnum; bool *final=new boolVexnum; int pathMaxLenMaxLen; int lenMaxLen; /给final初始化为false,将Matrix指定行的值赋给dist/path数组全部赋值为-1 for(i=-1;+iVexnum;) finali=false; disti=Matrixv0i; for

18、(j=-1;+jMaxLen;) pathij=-1; /如果dist中的值小于9999的话/path指定列赋值为v0/path的左上右下对角线赋值为v/指定顶点的长度赋值为Vexnum for(v=-1;+vVexnum;) /path的作用是一个顶点有一行，这一行里从左到右表示依次到达的结点/例如第二行下标为1/0 2 3 1表示从0到2到3到1/若为最终结果即为从0到1的所有路径中的最短路径/0行则没必要标出了。/path的赋值是从列开始的/这个时候dist0=9999 if(distvMaxDist) pathvv0=v0; pathvv=v; lenv=Vexnum; /dist指定

19、位置的值赋值为0/v0设置为已经访问 distv0=0; finalv0=true;/最小值等于9999/判断是否未访问/若未访问，如果distw小于最小值，就记录w和distw,分别赋给v和min/v位置为最小值的位置，设定为true/如果finalw未访问且最小值加上矩阵vw位置的值仍然小于distw/distw取值min+Matrixvw/然后领把v行的path值赋给w行/在w行末尾加个w/w行的长度等于v行加1 for(i=0;+iVexnum;) /跳过0/找到dist中的未被标记为true的最小值，然后标记为true，然后遍历邻接结点 min=MaxDist; for(w=-1;+

20、wVexnum;) if(!finalw) if(distwmin)v=w;min=distw;/if /for finalv=true; for(w=-1;+wVexnum;)/min+Matrixvwdistw有这个判断的原因是/比如我想从A点到B点，它的权值为30/但是我从A点先到C点，再到B点，它的权值和为25/那这样的话明显是先经过C点再到B点这个路径更好/!finalw是遍历其余的为遍历过的结点，避免与上一个已访问过的结点遍历 if(!finalw&(min+Matrixvwdistw) distw=min+Matrixvw; for(j=-1;+jlenv;) /赋值的原因是从这

21、个路径pathv(0-XXX-v)再到(w)能获得更短的路径 pathwj=pathvj; /for/在行尾加上当前结点，即从(0-XXX-v-w) pathwj=w; lenw=lenv+1; /if /for /for/输出 for(i=-1;+iVexnum;) if(i!=v0) coutv0-i-disti-; cout-; for(j=-1;+jMaxLen;) if(pathij!=-1) coutpathij ; /for coutt; for(k=0;kt;k+) for(i=0;iMaxLen;i+) for(j=0;jvnum; for(i=-1;+ivnum;) for(j=-1;+jmxij; myMap.SetMatrix(vnum,mx); cinv0; myMap.ShortestPath_DIJ(v0); return 0; 四、实验结