数 据 结 构 实 验 报 告 名 称：最小生成树 班 级：1 2 2 姓 名：* * * * * 学 号：* * * * * * * * * * * 指导老师：* * * * * * * * 2 一、设计目的与任务 1.1 课程设计目的 本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。 1.2 课程设计的任务 问题描述: 已知一个无向连通网表示 n 个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于 n 个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 二、设计方案 2.1 需求分析 （1） 建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表； （2） 利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树； （3） 输入 各 城市的数目以及各 个城市之间的距 离 。将 城市之间的距 离 当 做 网 中各 点之间的权值。按 顺 序输出生成树中各 条 边以及它 们的权值。 2.2 数据结构分析 构造 最小生成树的方法： 最初生成树为 空 ，即 没 有 一个结点和一条 边，首 先 选择一个顶点作 为 生成树的根 ，然 后 每次从 不在 生成树中的边中选择一条 权值尽 可能小的边，为 了保证 加 入 到 生成树中的边不会 造 成回 路，与该 边邻接的两个顶点必 须 一个已经 在 生成树中，一个则 不在 生成树中，若 网中 3 有n 个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1 边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2 个集合，U 集合中的元素是在生成树中的结点，V-U 集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U 集合，然后在那些一端顶点在U 集合中，而另一端顶点在V-U 集合中的边中找一条权最小的边，并把这条边和那个不在U 集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U 集合中，重复这个操作n-1 次。 弧的意义或信息} 2.3最小生成树的算法分析 在该函数中主要有五段代码块，分别是主函数代码块、邻接矩...
