2015广工数据结构实验报告无向图

《2015广工数据结构实验报告无向图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构设计性实验报告课程名称_____数据结构实验_题目名称无向图学生学院__计算机学院______专业班级__学号________学生姓名_____指导教师______2015年6月21日一．实验题目无向图（邻接数组实现）二．环境及工具环境：c++工具：codeblock三．存储结构定义头文件邻接数组边四．算法设计1.初始化n个顶点的空无向图2.查找顶点v在图G中的位序3.创建无向图4.销毁图5.取图G的k顶点的值到w6.对图G的k顶点赋值w7.求图G中k顶底的第一个邻接顶点的位序8.求图G中k顶点相对于m顶点的下一个邻接顶点的位序9.在图中增加k顶点到m顶点的

2、边或弧10.在图G中删除k顶点到m顶点的边或弧11.深度优先遍历图G12.从图G中的k顶点出发进行深度优先遍历13.判断图G是否存在从顶点s到t的路径14.广度优先搜索图G15.求图G中顶点s到各顶点的最短路径长度16.求图G中任意两点的最短路径17.用Prim算法从s顶点出发构造图G的最小生成树18.用Kruskal算法构造最小生成树五．测试构造一个图：512345个顶点，6条边。五个顶点：（1,2,3,4,5）边权为：（1,5）=6；（1,3）=2；（1,4）=3；（2,5）=3；（2,4）=2；（2,3）=1；初始化图：1.初始化n个顶点的空无向图测试程序测试

3、结果2.查找顶点v在图G中的位序测试程序测试结果1.创建无向图测试程序测试结果2.销毁图测试程序测试结果1.取图G的k顶点的值到w测试程序测试结果2.对图G的k顶点赋值w测试程序测试结果3.求图G中k顶底的第一个邻接顶点的位序测试程序测试结果1.求图G中k顶点相对于m顶点的下一个邻接顶点的位序测试程序测试结果2.在图中增加k顶点到m顶点的边或弧测试程序测试结果3.在图G中删除k顶点到m顶点的边或弧测试程序测试结果1.深度优先遍历图G测试程序测试结果2.从图G中的k顶点出发进行深度优先遍历测试程序测试结果1.判断图G是否存在从顶点s到t的路径测试程序测试结果2.广度优

4、先搜索图G测试程序测试结果1.求图G中顶点s到各顶点的最短路径长度测试程序测试结果2.求图G中任意两点的最短路径测试程序测试结果3.用Prim算法从s顶点出发构造图G的最小生成树测试程序测试结果1.用Kruskal算法构造最小生成树测试程序测试结果六．实验总结和体会本实验实现了无向图（邻接数组）的各种功能。通过我对函数块有了更深的理解，将功能分成多个函数进行实现，更有利于调试，单个查错测试，从而写出来庞大的程序。通过对各种功能的程序实现，我对无向图及其相关算法有了更深的理解，学到了很多东西。