1、 数据结构与算法数据结构与算法 课程设计课程设计报告报告 课程设计课程设计题目：题目： 最小生成树问题最小生成树问题 专业班级：专业班级： 信息信息与计算科学与计算科学 10100101 班班 姓姓 名：名： 学学 号：号： 设计室号：设计室号： 理学院机房理学院机房 设计时间：设计时间： 20201111- -1212- -2 26 6 批阅时间：批阅时间： 指导教师：指导教师： 成成 绩：绩： 一、一、摘要：摘要： 随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社 会生活的重要组成部分。我们希望拥有一个宽松的上网环境，以便更好的进行信 息的交流，在此我们有必要提升我们的网
2、络传播速度。从某种程度上来说网络传 播速度代表着一个国家网络化程度的高低。 为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网 络线路，以缓解网络不够流畅不够便捷的问题。而在城市之间架设网络线路受到 资金因素等的限制， 我们希望找到一条捷径这样我们即达到了连接了各个城市网 络的目的又节省了建设成本。 通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网 络的假设。在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网 络作为连接各个节点的边。于是我们就将城市的空间分布抽象成为一个网络图， 再将各条边的距离抽象成为各节点之间的权值。 在原来的基础上建立一个带有权
3、值的网络图。于是原有的问题就转化为找图的最小生成树问题。 我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。 二、问题分析二、问题分析 在 n 个城市间建立通信网络，需架设 n-1 条路线。求解如何以最低的经 济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法 或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市 之间的距离。将城市之间的距离当做网中各点之间的权值。 三、三、实现本程序需要解决的问题实现本程序需要解决的问题 （1）如何选择存储结构去建立一个带权的网络； （2）如何在所选存储结构下输出这个带权网络； （3）如何实现普利姆算法的功能； （
4、4）如何从每个顶点开始找到所有的最小生成树的顶点； （5）如何输出最小生成树的边及其权值 此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是 输出我们所需要的信息， 在此我们将各个城市看做是网中的各个顶点城市之间的 距离看做是个顶点之间的权值。现在我们问题做如下的分析： 这个问题主要在于普利姆算法的实现。我们将各个城市的空间分布抽象成一 个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的 各个顶点。 我们建立的输入的数据格式为：首先提示输入带权的顶点数目，我定义为整 形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整 数类型数据，这样我们就建立了一个带权的网络。 问题的输出我是将我们所得到的最小生成
