《图结构试验实验报告.pdf》由会员分享，可在线阅读，更多相关《图结构试验实验报告.pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 附件(四)深 圳 大 学 实 验 报 告 课程名称:数据结构实验与课程设计 实验项目名称:图结构实验 学院:计算机与软件学院 专业:指导教师:报告人:学号:班级:实验时间:实验报告提交时间:教务处制 一、实验目得与完成说明:1、简单介绍本实验得主要目得 2、说明您自己在本次实验中完成了第几项要求(必填)Contest1620-DS 实验 08-图遍历【11、12】Problem A:DS 图遍历-深度优先搜索 Description 主要目得:给出一个图得邻接矩阵,对图进行深度优先搜索,从顶点 0 开始(完成)注意:图 n 个顶点编号从 0 到 n-1 Input 第一行输入 t,表示有 t
2、 个测试实例(完成)第二行输入 n,表示第 1 个图有 n 个结点(完成)第三行起,每行输入邻接矩阵得一行,以此类推输入 n 行(完成)第 i 个结点与其她结点如果相连则为 1,无连接则为 0,数据之间用空格隔开(完成)以此类推输入下一个示例(完成)Output 每行输出一个图得深度优先搜索结果,结点编号之间用空格隔开(完成)Problem B:DS 图遍历-广度优先搜索 Description 给出一个图得邻接矩阵,对图进行深度优先搜索,从顶点 0 开始(完成)注意:图 n 个顶点编号从 0 到 n-1 Input 第一行输入 t,表示有 t 个测试实例(完成)第二行输入 n,表示第 1 个
3、图有 n 个结点(完成)第三行起,每行输入邻接矩阵得一行,以此类推输入 n 行(完成)第 i 个结点与其她结点如果相连则为 1,无连接则为 0,数据之间用空格隔开(完成)以此类推输入下一个示例 Output 每行输出一个图得广度优先搜索结果,结点编号之间用空格隔开(完成)Contest1638-DS 实验 09-最短路径【11、19】Problem A:DS 图应用-最短路径 Description 给出一个图得邻接矩阵,再给出指定顶点v0,求顶点v0 到其她顶点得最短路径(完成)Input 第一行输入 t,表示有 t 个测试实例(完成)第二行输入 n,表示第 1 个图有 n 个结点(完成)第
4、三行起,每行输入邻接矩阵得一行,以此类推输入 n 行(完成)第 i 个结点与其她结点如果相连则为 1,无连接则为 0,数据之间用空格隔开 第四行输入 v0,表示求 v0 到其她顶点得最短路径距离(完成)以此类推输入下一个示例 Output 每行输出 v0 到某个顶点得最短距离与最短路径(完成)每行格式:v0 编号-其她顶点编号-最短路径,具体请参考示范数据(完成)二、主要思路与方法:1、对于本次实验,说明您认为最重要得函数、算法或知识点,并谈谈您对它们得理解 Contest1620-DS 实验 08-图遍历【11、12】Problem A:DS 图遍历-深度优先搜索 从 0 开始连续获取邻接结
5、点,然后逐个遍历并设 Visit 为 true 避免重复遍历 Problem B:DS 图遍历-广度优先搜索 首先将该顶点得邻接顶点全部入队,然后挨个读取,在读取得过程中继续将邻接矩阵入队,并把已经读取过得顶点全被设为 true。Contest1638-DS 实验 09-最短路径【11、19】Problem A:DS 图应用-最短路径 输入 mx 矩阵 Mx 0 1 2 3 4 0 0 5 0 7 15 1 0 0 5 0 0 2 0 0 0 0 1 3 0 0 2 0 0 4 0 0 0 0 0 初始化并赋值 Matrix 得矩阵 Matrix 0 1 2 3 4 0 3 1 2 0 4 3
6、 2 1 0 4 3 2 1 0 3 1 2 1 2 0 3 4 1 5 2 7 5 15 0 5 7 15 1 5 2 1 3 2 4 初始化并赋值 path 得矩阵 Path 0 1 2 3 4 0-1-1-1-1-1 1 0 1-1-1-1 2-1-1-1-1-1 3 0-1-1 3-1 4 0-1-1-1 4 初始化并赋值 dist 数组 Dist 0 1 2 3 4 5 7 15 初始并赋值 len 数组 Len 0 1 2 3 4 5 5 5 5 5 i=1 得时候;min=9999;v=1;min=5;final1=true;521 可以访问。Dist2=5+Matrix12=1
7、0;2=1;Path 数组改变 Path 0 1 2 3 4 5 0-1-1-1-1-1 1 0 1-1-1-1 2 0 1-1-1-1 2 3 0-1-1 3-1 4 0-1-1-1 4 Dist 数组改变 Dist 0 1 2 3 4 5 10 7 15 v=3;min=7;final3=true;223 可以访问。Dist2=7+Matrix32=9;2=3;Path 数组改变 Path 0 1 2 3 4 5 0-1-1-1-1-1 1 0 1-1-1-1 2 0-1-1 3-1 2 3 0-1-1 3-1 4 0-1-1-1 4 Dist 数组改变 Dist 0 1 2 3 4 5
8、9 7 15 v=2;min=9;final2=true;142 可以访问。Dist4=9+Matrix24=10;4=2;Path 数组改变 Path 0 1 2 3 4 5 6 0-1-1-1-1-1 1 0 1-1-1-1 2 0-1-1 3-1 2 3 0-1-1 3-1 4 0-1-1 3-1 2 4 Dist 数组改变 Dist 0 1 2 3 4 5 9 7 10 三.实验程序或内容:1、针对每一项实验要求,给出编写得代码,2、可以粘贴全部代码,或者可以只粘贴重要得代码(为了节省纸张),但代码必须完整,至少就是完整得函数。3、代码符合以下要求,评分更高:a、排版整齐,可读性高 b
9、、代码有注释,越详细越清晰越好 Contest1620-DS 实验 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
10、(int vnum,int mxMaxLenMaxLen)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;
11、void Map: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#include usin
12、g 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 mxMaxLenMaxLen)int i,j;Vexnum=vnum
13、;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;coutv;int*AdjVex=new intVexnum;for(i=-1;+iVexnu
14、m;)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;for(i=-1;+iVexnum;)Visiti=false;/for for(i=-1;+iVexnum;)AdjVexi=-1;f
15、or(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、push(w);/if /for /while /if /for coutt;while(t-)cinn;int mx2020;for(i=-1;+in;)for(j=-1;+jmxij;
16、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 MatrixMaxLenMaxLen;int Vexnum;public:void SetMatrix(int vnum,int mxMaxLenMaxLen);void ShortestPath_DIJ(int v0)
17、;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;+iVexnum;)for(j=-1;+jVexnum;)if(mxij)Matrixij=mxij;void Map:ShortestPath_DIJ(int v0)int i,j,v,w,min;int*dist=new i
18、ntVexnum;bool*final=new boolVexnum;int pathMaxLenMaxLen;int lenMaxLen;/给 final 初始化为 false,将 Matrix 指定行得值赋给 dist /path 数组全部赋值为-1 for(i=-1;+iVexnum;)finali=false;disti=Matrixv0i;for(j=-1;+jMaxLen;)pathij=-1;/如果 dist 中得值小于 9999 得话 /path 指定列赋值为 v0 /path 得左上右下对角线赋值为 v /指定顶点得长度赋值为 Vexnum for(v=-1;+vVexnum
19、;)/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 指定位置得值赋值为 0 /v0 设置为已经访问 distv0=0;finalv0=true;/最小值等于 9999 /判断就是否未访问 /若未访问,如果 distw小于最小值,就记录 w
20、 与 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;+wVexnum;)if(!finalw)if(distwmin)v=w;min=distw;/
21、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;)/赋值得原因就是从这个路径 pathv(0-XXX-v)再到(w)能获得更短
22、得路径 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);cinv
23、0;myMap、ShortestPath_DIJ(v0);return 0;四、实验结论:1、根据您完成得每个实验要求,给出相应得实验结果图,并结合图来解析运行过程 2、如果运行过程简单,只要贴出 VC 运行得结果图。3、如果无结果图,有网站得判定结果,贴出相应结果 Contest1620-DS 实验 08-图遍历【11、12】Problem A:DS 图遍历-深度优先搜索 Sample Input 2 4 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 5 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 Sample Out
24、put 0 2 1 3 0 3 2 1 4 Problem B:DS 图遍历-广度优先搜索 Sample Input 2 4 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 5 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 Sample Output 0 2 3 1 0 3 4 2 1 Contest1638-DS 实验 09-最短路径【11、19】Problem A:DS 图应用-最短路径 Sample Input 1 5 0 5 0 7 15 0 0 5 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 Sample Output 0-1-5-0 1 0-2-9-0 3 2 0-3-7-0 3 0-4-10-0 3 2 4 五、实验体会:(根据自己情况填写)图得遍历适用于网络地图。图得最小路径适合在地图上寻找最佳路径。目前数据结构得顺序就是一对一(线性表),一对多(树),多对多(图)。注:“指导教师批阅意见”栏请单独放置一页 指导教师批阅意见:成绩评定:指导教师签字:年 月 日 备注: