欢迎来到天天文库
浏览记录
ID:60850353
大小:93.00 KB
页数:15页
时间:2020-12-23
《北邮数据结构实验 第二次实验 图教学内容.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、…………………………………………………………最新精品资料推荐……………………………………………………数据结构实验报告1.实验要求(1)实验目的通过选择下面5个题目之一进行实现,掌握如下内容:Ø掌握图基本操作的实现方法Ø了解最小生成树的思想和相关概念Ø了解最短路径的思想和相关概念Ø学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义,使用邻接矩阵或邻接表实现一个图。图的基本功能:1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小
2、生成树7、求指定顶点到其他各顶点的最短路径8、其他:比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析2.1存储结构图:(1)带权值的无向图V096V12V2(2)带权值的有向图V0…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………6394V12V22.2关键算法分析(1)深度优先遍历intvisited[MAXSIZE]={false
3、};templatevoidMGraph::DFS(intv){cout<4、=0;j…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐………5、……………………………………………intmininum(MGraphG,inta[]){intmin=MAX;intk=0;for(inti=0;ivoidMGraph::Prim(MGraphG){for(inti=0;i6、i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iV"<7、²)(4)克鲁斯卡尔算法templatevoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………{intk=0,i,j;for(i=0;i8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2
4、=0;j…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐………
5、……………………………………………intmininum(MGraphG,inta[]){intmin=MAX;intk=0;for(inti=0;ivoidMGraph::Prim(MGraphG){for(inti=0;i6、i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iV"<7、²)(4)克鲁斯卡尔算法templatevoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………{intk=0,i,j;for(i=0;i8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2
6、i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iV"<7、²)(4)克鲁斯卡尔算法templatevoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………{intk=0,i,j;for(i=0;i8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2
7、²)(4)克鲁斯卡尔算法templatevoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………{intk=0,i,j;for(i=0;i8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2
8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2
此文档下载收益归作者所有