《数据结构》课程设计--最小生成树问题

《《数据结构》课程设计--最小生成树问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名:XXX班级：XXX学号:XXXXXXXXX起迄日期:2015.07.13-2015.07.24指导教师:XXXXXX任务书最小生成树问题[问题描述]在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。[设计要求]（1）通过输入建立一无向网，存储结构可以采用多种；（2）要求分别采用普里姆算法和克鲁斯卡尔算法实现；（3）若以图形界面输出可以适当加分。 54一、需求分析1.问题描述：该程序主要实现最小生成树功能，在给定的中国铁路网中，选择城市，生成最小生成树。此

2、外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离等图论的基本操作。直观、清晰的为用户提供全国铁路网的最基本情况。该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。输入指定的城市求出最小生成树，方便查询城市间的最短连通量。另外添加了显示全国主要铁路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介绍。该程序实现了指定城市到其它城市之间的最短距离。通过在地图上选择城市，程序通过Dijkstra算法计算出指定城市到其它城市之间的最短距离，并通过te

3、xtBox控件显示，一目了然。具有较强的人机和谐性。还可以实现指定城市之间的最短路，输入两个指定的城市，通过Floyd算法求出选定城市间的最短距离。并在图形界面上标注要经过的城市。2.基本功能：（1）通过输入建立一无向网，存储结构采用了邻接矩阵。（2）要求分别采用Prim算法和Kruskal算法实现，分别对应Prim.cs和Kruskal.cs。（3）若以图形界面输出会适当加分。3.附加功能：（1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介绍。主要实现代码在Map.cs中。（2）指定城市到其它城市的最短距离，在

4、地图上点击指定城市，程序会显示指定城市到其它城市的最短距离。主要实现代码在Dijkstra.cs中（3）指定的两个城市之间的最短距离。在地图中选择两个城市，程序会显示这两个城市之间的最短距离，并在地图上显示在这两个城市之间经过的城市。主要实现代码在LeastRoad.cs中。二、概要设计1.设计思路：首先，将城市和道路的主要信息，包括城市和道路的数量、城市的名称、道路的相关信息存入文件中。在每个程序模块中通过字节流StreamReader从文件中读取字符，放入程序定义的存储结构中。（1）城市介绍。地图所含城市的主要介绍和城市名存入文本文件

5、c5.txt中，在Map.cs中定义选定城市的关键字T，读取文件中的内容，寻找关键字T相对应的城市名，并在textBox1中输出该城市的相关内容。（2）54指定城市到其它城市的最短路。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数量、城市名称、道路的相关信息。存于指定的变量中。采用Dijkstra算法求出指定城市到其它城市的最短路，存入指定变量中。Dijkstra算法用于求某个顶点到其余各顶点的最短路径。（1）指定城市之间的最短路。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数量、城市名称、

6、道路的相关信息。存于指定的变量中。在给定的图中选择两个城市，存入相应的变量中。采用Floyd算法求出指定城市之间的最短路径。Floyd算法用于求每一对顶点之间的最短路径。（2）最小生成树(Prim)。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数量、城市名称、道路的相关信息，存于指定的变量中。在给定的图中选择城市，存入相应的变量中。采用Prim算法求出最小生成树。Prim算法通过寻找最小的距离，生成最小生成树。（3）最小生成树（Kruskal）。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数

7、量、城市名称、道路的相关信息，存于指定的变量中。在给定的图中选择城市，存入相应的变量中。采用Kruskal算法求出最小生成树。Kruskal算法通过寻找最小的边的操作，生成最小生成树。2.数据结构设计：逻辑结构：图状该程序主要实现最小生成树、指定顶点间的最短距离。题目的设计要求决定，图的存储结构是最理想的选择。其次，采用图状结构，更加适用于本程序，更形象化。便于整个程序代码的编写。为之后的功能设计提供方便。存储结构：顺序。链式存储结构，具有操作灵活、简便等特点。由于程序采用C#语言设计。在C#中没有指针这一类型。虽然可以通过类的定义实现链

8、式存储，但操作过于麻烦，容易造成隐藏的错误。所以采用顺序存储结构。采用顺序存储结构也可以实现图的存储，进而进行之后的一些列操作。相比于链式，顺序存储结构在一些算法的设计上，所消耗的时间可能会更