最小生成树实验报告.doc

.数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期: 指导教师: 20112012年度 第 2 学期 一、需求分析1.问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。二、 概要设计1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所 以我选择采用了邻接表和邻接