《实验8图的最小生成树问题》由会员分享,可在线阅读,更多相关《实验8图的最小生成树问题(2页珍藏版)》请在金锄头文库上搜索。
1、1浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验八 图的最小生成树 学生姓名 专业班级 学号 实验成绩 指导老师(签名 ) 日期 一. 实验目的和要求1. 掌握图的最小生成树的概念。2. 掌握生成最小生成树的 Prim 算法(用邻接矩阵表示图)。二. 实验内容1、 编写用邻接矩阵表示无向带权图时图的基本操作的实现函数,主要包括:初始化邻接矩阵表示的无向带权图 void InitMatrix(adjmatrix G); 建立邻接矩阵表示的无向带权图 void CreateMatrix(adjmatrix G, int n) (即通过输入图的每条边建立图的邻接矩阵); 输出邻
2、接矩阵表示的无向带权图 void PrintMatrix(adjmatrix G, int n) (即输出图的每条边)。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件 Graph1.h 中。2、 编写生成最小生成树的 Prim 算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组 的函数 void PrintEdge(edgeset CT, int n)。3、 编写测试程序(即主函数),通过调用上述函数首先建立并输出无向带权图,然后生成最小生成树并输出(即输出边集)。 要求:把边集数组的结构定义、Prim 算法函数、输出边集数组的函数PrintEdge 以及 主函数存放在文件 test8.cpp 中。测试数据如下:0123545812310 76 2961524、 填写实验报告,实验报告文件取名为 report8.doc。5、上传实验报告文件 report8.doc 与源程序文件 test8.cpp 及 Graph1.h 到Ftp 服务器上自己的文件夹下。三. 函数的功能说明及算法思路包括每个函数的功能说明,及一些重要函数的算法实现思路四. 实验结果与分析包括运行结果截图等五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】