下载文档原格式
数据结构课程设计报告起评分理论成绩实践成绩总成绩院系：专业：班级：学号：姓名：教师：时间：目录一、设计要求 (3)1、问题描述 (3)2、功能 (3)3、数据 (3)二、概述与分析 (3)1、图 (3)2、邻接矩阵 (3)3、生成树 (4)4、最小生成树 (5)5、最小生成树的操作 (5)三、程序设计及分析 (6)四、流程图 (7)1、模块结构流程图 (7)2、Prim算法流程设计 (8)五、测试分析 (8)六、总结 (10)七、源程序代码 (10)一、设计要求：1、问题描述构造可以使n个城市连接的最小生成树。
2、功能给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
本人采用的是Prim算法。
3、数据城市间的距离网采用邻接矩阵表示（要求至少6个城市，10条边），邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）二、概述与分析1、图图的定义：图G是有两个集合V和E组成，记做G=（V,E），其中V是定点的有限集合，记做V(G)，E是连接V的两个不同的顶点的边的有限集合，记做E(G)。
2、邻接矩阵邻接矩阵是图的一种存储方法，它是表示顶点之间相邻关系的矩阵。
设G=(V,E)是具有n(n>0)个顶点的图，顶点的顺序依次为（v0,v1,…,vn-1）,则G的邻接矩阵A是n阶方阵，其定义如下。
1)如果G是无向图，则1 (vi,vj) ∈E(G)A[i][j]=0 其他2)如果G是有向图，则1 <vi,vj> ∈E(G)A[i][j]=0其他3)如果G是带权无向图，则w ij vi≠vj且（vi,vj）∈E(G)A[i][j]= 0 vi =vj∞其他4)如果G是带权有向图，则w ij vi≠vj且<vi,vj> ∈E(G)A[i][j]= 0 vi =vj∞其他邻接矩阵的特点如下：1）图的邻接矩阵表示是唯一的。
数据结构课程设计报告起评分理论成绩实践成绩总成绩院系：专业：班级：学号：：教师：时间：目录一、设计要求 (3)1、问题描述 (3)2、功能 (3)3、数据 (3)二、概述与分析 (3)1、图 (3)2、邻接矩阵 (3)3、生成树 (4)4、最小生成树 (5)5、最小生成树的操作 (5)三、程序设计及分析 (6)四、流程图 (7)1、模块结构流程图 (7)2、Prim算法流程设计 (8)五、测试分析 (8)六、总结 (10)七、源程序代码 (10)一、设计要求：1、问题描述构造可以使n个城市连接的最小生成树。
2、功能给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
本人采用的是Prim算法。
3、数据城市间的距离网采用邻接矩阵表示（要求至少6个城市，10条边），邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）二、概述与分析1、图图的定义：图G是有两个集合V和E组成，记做G=（V,E），其中V是定点的有限集合，记做V(G)，E是连接V的两个不同的顶点的边的有限集合，记做E(G)。
2、邻接矩阵邻接矩阵是图的一种存储方法，它是表示顶点之间相邻关系的矩阵。
设G=(V,E)是具有n(n>0)个顶点的图，顶点的顺序依次为（v0,v1,…,vn-1）,则G的邻接矩阵A是n阶方阵，其定义如下。
1)如果G是无向图，则1 (vi,vj) ∈E(G)A[i][j]=0 其他2)如果G是有向图，则1 <vi,vj> ∈E(G)A[i][j]=0其他3)如果G是带权无向图，则w ij vi≠vj且（vi,vj）∈E(G)A[i][j]= 0 vi =vj∞其他4)如果G是带权有向图，则w ij vi≠vj且<vi,vj> ∈E(G)A[i][j]= 0 vi =vj∞其他邻接矩阵的特点如下：1）图的邻接矩阵表示是唯一的。
武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：09计科2班学生姓名：蒋家权，陈相财，吴继伟，梁丽春指导教师：林丽惠完成日期：2011-1-19课程设计项目研究报告目录一、问题分析和任务定义....................................................................................... - 1 -二、实现本程序需要解决的问题如下................................................................... - 1 -三、测试数据........................................................................................................... - 2 -四、算法思想........................................................................................................... - 3 -五、模块划分........................................................................................................... - 4 -六、算法设计与分析............................................................................................... - 7 -七、源程序............................................................................................................. - 11 -八、测试数据......................................................................................................... - 14 -九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 -十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。
实验5 最小生成树算法的设计与实现一、实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。
二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。
有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。
设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。
三、Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53 4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U={}不属于最小生成树的顶点V={1，2，3，4，5，6}2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成四、实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； //定义比较方法x)；//在并查集森林中找到x的祖先int g etfa(intint s ame(int x,int y)； //判断祖先是否是同一个，即是否联通 void merge(int x,int y); //合并子树，即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M AXN_E 100000#define M AXN_V 100000using namespace std;struct Edge{int f m,to,dist;//边的起始顶点，边的到达顶点，边权}e[MAXN_E];int f a[MAXN_V],n,m; //顶点数组，顶点总数，边总数 //定义比较，只是边权比较bool cmp(Edge a,Edge b){return a.dist < b.dist;}//查找x的祖先是在并查集森林中找到x的祖先x){//getfaint g etfa(intreturn fa[x];if(fa[x]==x)else r eturn fa[x] = getfa(fa[x]);}//判断祖先是否是同一个，即是否联通int s ame(int x,int y){return getfa(x)==getfa(y);}//合并两棵树void merge(int x,int y){int f ax=getfa(x),fay=getfa(y);fa[fax]=fay;}int m ain(){int i;cout<<"请输入顶点数目和边数目："<<endl;cin>>n>>m;//n为点数，m为边数//输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i++){fa[i]=i;if(i!=0)cout<<fa[i]<<" ";}cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl;for(i=1;i<=m;i++)用边集数组存放边，方便排序和调用 cin>>e[i].fm>>e[i].to>>e[i].dist;//sort(e+1,e+m+1,cmp); //对边按边权进行升序排序表示目前的点共存在于多少个集合中，初始情况是每 int r st=n,ans=0;//rst个点都在不同的集合中for(i=1;i<=m && rst>1;i++){int x=e[i].fm,y=e[i].to;函数是查询两个点是否在同一集合中 if(same(x,y))continue;//sameelse{函数用来将两个点合并到同一集合中 merge(x,y);//mergerst--;//每次将两个不同集合中的点合并，都将使rst值减1这条边是最小生成树中的边，将答案加上边权 ans+=e[i].dist;//}}cout<<ans;return 0;}五、测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。
数据结构与算法课程设计报告书题目：n个城市连接的最小生成树班级：1101211学号：1110121137姓名：小张教师：周期：2013年6月4日——6月28 （以下由验收教师填写）成绩：2013 年6月27日提问：使用的什么算法？好处？都实现了哪些功能？在程序的哪里体现的？《n个城市连接的最小生成树》一、课程设计的目的与要求（一）课程设计目的与任务（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本上的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括那些城市间的道路，并显示得到的最小生成树的代价。
（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
（二）题目要求对所选题目，运用面向过程的分析与设计方法，给出系统分析与设计的结果，要求必须要运用数据结构课程中相关的基本知识；二、设计正文1 系统分析和开发背景按照题目要求需要采用邻接矩阵来存放城市间的距离网，且用Prim算法建立最小生成树并求最小生成树代价。
图的结点信息存放在一个顺序表中，图的边信息存储在一个二维数组edge[MaxVertices][MaxVertices]中，这样就实现了用邻接矩阵存放城市间的距离网。
在Prim算法的函数用两个参数，一个是图G为邻接矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.2 功能详细描述输入城市数，显示个城市间的距离，显示最小生成树3、数据结构和数据库设计顺序表定义结构体如下：Typedef struct{DataType list[Maxsize];Int size;}SeqList;其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size<= Maxsize，SeqList是该结构体的名称。
课程设计报告问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。
对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。
我们要选择一棵生成树，使总的耗费最小（1）需求分析：在N地建设网络保证连通即可求最小的架设方式，任务完成可分为两个部分：A 存储N中任意两地之间的权（采用邻接表，邻接矩阵）B 用prim和克鲁斯卡尔两种算法分别求出N地中最优架设方式即最小生成树。
C 按顺序输出生成树中各条边以及它们的权值。
（2）概要设计：程序分为两大部分 1 存储部分，2 算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。
Prim算法的思想：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u 0},TE={f}。
此步骤设立一个只有结点u 0的结点集U 和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。
2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。
此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。
找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。
这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。
3:如果U=V,则算法结束;否则重复步骤2。
可以把本步骤看成循环终止条件。
我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
《数据结构》课程设计报告设计题目：构造可以使n个城市连接的最小生成树姓名：学号：专业：物联网工程（嵌入式培养）院系：计算机技术与科学学院班级：1405指导教师：2016年01 月09 日摘要本次课程设计的要求是给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点A到顶点B的所有路径中，边的权值之和最少的那条路径。
关键词：最小生成树Prim算法C++语言源程序AbstractThe curriculum design requirements is given a region n city, the distance between the net with the Prim algorithm to establish minimum spanning tree, and calculated the price of minimum spanning tree. Cities in the region with vertex said, between highway in the city edge, said the length of the road as the edge of the right values, finally the problem can be summed up in network diagram, and all the paths of vertex A to B, the edge of the weights of the sum of the minimum path.Keywords:minimum spanning treePrim algorithmC++ language source program目录一、问题描述 (4)1.1题目内容 (4)1.2基本要求 (4)二、需求分析 (4)三、概要设计 (4)3.1邻接矩阵的建立 (5)3.2图的建立 (5)3.3求最小生成树 (6)四、数据结构设计 (7)五、算法设计 (8)5.1算法分析 (8)5.2算法实现 (8)六、程序测试与实现 (9)6.1主程序 (9)6.2测试结果 (10)七、调试分析 (10)八、遇到的问题及解决办法 (10)九、心得体会 (10)十、附录 (11)一、问题描述1．题目内容：给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第 2 学期一、需求分析1.问题描述：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
存储结构采用多种。
求解算法多种。
该题目需要运用最小生成树来解决。
最小生成树的代价之和最小，所以是一种最经济的架设方法。
2.基本功能该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。
3.输入输出首先输入顶点的个数以及边的个数，格式如:4 6。
然后输入边的权值，格式如：a b 1。
输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。
最小生成树的格式为：<顶点名顶点名>权值。
二、概要设计1.设计思路：问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。
1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。
然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。
2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
2.数据结构设计：1.抽象数据类型如下：ADT Graph{ 数据对象 V：v是具有相同特征的数据元素的集合，称为顶点集。
数据关系 R：R={VR}VR={<v,w>|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧<v,w>的意义或信息}基本操作：1)GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。
操作条件：按V和VR的定义构造图G。
2）LocateVex（G,u）；初始条件：图G存在，u和G中顶点有相同的特征。
操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第 2 学期一、需求分析1.问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
存储结构采用多种。
求解算法多种。
2.基本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。
程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。
3.输入输出以文本形式输出最小生成树，同时输出它们的权值。
通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。
二、概要设计1.设计思路：因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。
根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。
2.数据结构设计：图状结构：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}VR={<v,w>|v,w∈V且P(v,w)，<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph( &G )初始条件：图G存在。
操作结果：销毁图G。
LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。
GetVex( G, v )初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。
操作结果：对v赋值value。
数据结构实验最小生成树数据结构实验报告最小生成树问题一、问题描述:若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题基本要求(1)从文件中读入图的信息。
(2)利用克鲁斯卡尔算法求网的最小生成树。
(3)以文本形式生成树中各条边以及他们的权值。
二(需求分析:1、需定义结构体数组，根据权值逐一选择边。
三(概要设计抽象数据类型:需定义结构体数组，存储每条边的起点，终点，权值。
算法的基本思想:1、图的信息的读取:定义结构体数组，存储每条边的起点，终点，权值。
2、对每条边在数组中的位置处理:选边需从最小的开始，故按边的权值从小到大进行排序。
3、边的选取: 从最小的边的开始，若边的两端点不属于同一集合，则选取该边。
并将该边的两个顶点所在的两个集合合并成为一个。
因为有n个顶点，故只需选取n-1条边。
程序的流程:(1) 输入模块: 读入图的信息(顶点和边，用结构体数组进行存储)。
(2) 处理模块:Kruskal算法。
(3) 输出模块:将结果输出。
四(详细设计:算法的具体步骤:struct G{int fromvex;int endvex;int weight;}GE[100],cur[100];void swap(G* GE,int i,int j){ //交换函数int temp=GE[i].fromvex;GE[i].fromvex=GE[j].fromvex;GE[j].fromvex=temp;temp=GE[i].endvex;GE[i].endvex=GE[j].endvex;GE[j].endvex=temp;temp=GE[i].weight;GE[i].weight=GE[j].weight;GE[j].weight=temp;}void Kruskal(int n){int i,j,k=0,pos=-1,m1,m2;bool** s=new bool *[n];//定义一个二维数组，用来判断是否为同一类for(i=0;i<n;i++)s[i]=new bool[n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=true; //初始化数组elses[i][j]=false;}}while(k<n-1){for(i=0;i<n;i++){if(s[i][GE[k].fromvex]==1)m1=i;if(s[i][GE[k].endvex]==1)m2=i;}if(m1!=m2){//判断是否为同一类,如果为同一类(该类中所有的点到起点和终//点的边在s 数组中赋为1)，cur[++pos].fromvex=GE[k].fromvex;cur[pos].endvex=GE[k].endvex;cur[pos].weight=GE[k].weight;for(i=0;i<n;i++){if(s[m1][i] || s[m2][i])//把该点添加到该类，并和并两个类s[m1][i]=1;elses[m1][i]=0;s[m2][i]=0;}}k++;}for(i=0;i<n;i++){delete []s[i];}}int main(){int i,j;int numVertex,numEdge;cout<<"请输入点的个数和边的条数:"<<endl; cin>>numVertex>>numEdge;cout<<"请输入边的起始位置和边的权值:"<<endl;for(i=0;i<numEdge;i++)cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;for(i=0;i<numEdge;i++)for(j=i;j<numEdge;j++){if(GE[j].weight<GE[i].weight)//将边的权值按从小到大排列swap(GE,i,j);}Kruskal(numEdge);for(i=0;i<numVertex-1;i++) cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;system("pause");return 0;}五(调试分析:将选边的过程输出来检验算法的正确性。
数据结构实验报告名称：最小生成树班级:122姓名：＊*＊＊*学号：*＊**＊＊＊*＊*＊指导老师：***＊**＊*一、设计目的与任务1。
1课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。
1。
2课程设计的任务问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价.对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。
我们要选择一棵生成树，使总的耗费最小。
二、设计方案2。
1需求分析（1）建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表；（2）利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树；（3）输入各城市的数目以及各个城市之间的距离。
将城市之间的距离当做网中各点之间的权值。
按顺序输出生成树中各条边以及它们的权值。
2.2数据结构分析构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根,然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图）,则按这种条件选择n—1边就可以得到这个网的最小生成树了。
详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V—U集合中的元素是不在生成树中的顶点。
首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。
数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名: XXX班级： XXX 学号: XXXXXXXXX起迄日期: 2015.07.13-2015.07.24指导教师: XXX XXX任务书最小生成树问题[问题描述]在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
[设计要求]（1）通过输入建立一无向网，存储结构可以采用多种；（2）要求分别采用普里姆算法和克鲁斯卡尔算法实现；（3）若以图形界面输出可以适当加分。
一、需求分析1.问题描述：该程序主要实现最小生成树功能，在给定的中国铁路网中，选择城市，生成最小生成树。
此外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离等图论的基本操作。
直观、清晰的为用户提供全国铁路网的最基本情况。
该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。
输入指定的城市求出最小生成树，方便查询城市间的最短连通量。
另外添加了显示全国主要铁路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介绍。
该程序实现了指定城市到其它城市之间的最短距离。
通过在地图上选择城市，程序通过Dijkstra算法计算出指定城市到其它城市之间的最短距离，并通过textBox控件显示，一目了然。
具有较强的人机和谐性。
还可以实现指定城市之间的最短路，输入两个指定的城市，通过Floyd算法求出选定城市间的最短距离。
并在图形界面上标注要经过的城市。
2.基本功能：（1）通过输入建立一无向网，存储结构采用了邻接矩阵。
（2）要求分别采用Prim算法和Kruskal算法实现，分别对应Prim.cs和Kruskal.cs。
（3）若以图形界面输出会适当加分。
3.附加功能：（1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介绍。
主要实现代码在Map.cs中。
（2）指定城市到其它城市的最短距离，在地图上点击指定城市，程序会显示指定城市到其它城市的最短距离。
数据结构课程设计说明书学院：信息科学与工程学院班级：计算机11-2完成人：姓名：学号：************ 姓名：学号：************ 指导教师：山东科技大学2012年12月13日课程设计任务书一、课程设计题目：构造可以使n个城市连接的最小生成树二、课程设计应解决的主要问题：（1）邻接矩阵的构造及其存储（2）判断是否能够生成最小生成树（3）克鲁斯算法的设计（4）利用克鲁斯算法构造最小生成树时是否产生回路的判断（5）界面的设计三、任务发出日期：2012-11-28 课程设计完成日期：2012-12-13小组分工说明小组编号 35 题目：构造可使n个城市连接的最小生成树小组分工情况：王露：算法设计，void Kruskal()函数，void set ()函数，void find()函数，void Union()函数王炜程：void creat()函数，void judge()函数，int main()函数；int menu()函数，void display()函数组长签字：年月日指导教师对课程设计的评价成绩：指导教师签字：年月日目录一、主要问题------------------------------------------------------------------5二、基本要求------------------------------------------------------------------5三、算法基本思想描述------------------------------------------------------5四、详细设计------------------------------------------------------------------51、数据结构的设计----------------------------------------- 5<1> 存储结构------------------------------------------------------- 5<2> 图的表示--------------------------------------------------------62、算法的设计---------------------------------------------6<1> 克鲁斯卡尔算法设计----------------------------------------------6<2> 防止不能构成最小生成树的图--------------------------------------6<3> 模块结构及功能-------------------------------------------------- 7<4> 主要模块算法描述------------------------------------------------ 7五、源程序清单-----------------------------------------------------------------9六、测试数据及测试结果-----------------------------------------------------91、开始画面--------------------------------------------------------- 92、输入信息--------------------------------------------------------- 103、数据处理---------------------------------------------------------10（1）判断能否构成最小生成树--------------------------------------- 10（2）遍历所有的最小生成树----------------------------------------- 10（3）退出--------------------------------------------------------- 11七、课程设计总结--------------------------------------------------------------11八、附录--------------------------------------------------------------------------------11 参考书目--------------------------------------------------------------------------15构造可以使n个城市连接的最小生成树一、主要问题给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
HUNAN UNIVERSITY 课程实习报告
题目：最小生成树
学生姓名：
学生学号：
专业班级：
指导老师：
完成日期：
一、需求分析
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题
二、概要设计
抽象数据类型
用数组将边的距离及权值进行存储并排序。
算法的基本思想
构造生成树的网一定是无向网。
并设顶点数不超过30个，边权值为小于100的整数。
根据克鲁斯卡尔算法的特点，为便于选择选择权值小的边，存储结构不选用邻接矩阵和邻接表，而是可以用存储边（带权）的数组表示图。
程序的流程
程序由三个模块构成：
（1）从文件中读入图的信息。
（2）利用克鲁斯卡尔算法求网的最小生成树。
（3）以文本形式生成树中各条边以及他们的权值。
三、
四、详细设计
算法的具体步骤
先将用户的输入的顶点和边的数量，根据这些信息构建出图的结构，最后对边的权值进行排序。
输入和输出的格式
输入：
输入顶点和边的个数及顶点之间的权值。
输出：
输出最小生成树的序列。
五、测试结果
六、实验心得
实验的时候不是这个结果啊，可能是哪个环节出了错误，但是思想没有问题的，通过本次实验学会了用C++实现最小生成树。
友情提示：范文可能无法思考和涵盖全面，供参考!最好找专业人士起草或审核后使用，感谢您的下载！。
《数据结构》课程设计报告构造可以使n个城市连接的最小生成树学校：平顶山学院设计题目（问题）描述和要求给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
二、系统分析与概要设计根据问题描述和要求，系统要求能够显示最小生成树的边，权值和得到的最小生成树的代价。
确定程序的数据结构（抽象数据类型）及“邻接矩阵的数据类型”、“临时数组的存放的数据类型”、邻接矩阵的创建等各模块定义。
做此设计，城市间的道路网用邻接矩阵来表示。
若两个城市之间不存在道路，则将相应的权值设置为自己定义的无穷大值。
此程序的目的是：显示最小生成树的边，权值和得到的最小生成树的代价。
因此该程序的指令是：输入城市数和道路数—>输入城市名—>输入道路信息—>执行prim算法—>输出最小生成树。
三、详细设计和编码1、邻接矩阵的数据类型的定义如下：typedef struct{ int no; /*顶点编号*/string name; /*顶点其他信息*/ } VertexType; /*顶点类型*/typedef struct{ int edges[MAXV][MAXV]; /*邻接矩阵*/int vexnum,arcnum; /*顶点数,弧数*/VertexType vexs[MAXV]; /*存放顶点信息*/ }MGraph;2、临时数组的存放的数据类型struct {int closest; // U集中的顶点序号int lowcost; // 边的权值} closedge[MAXV];int const INF=32767; /*INF表示∞*/3、prime算法实现：（原理见实验说明）void prime(MGraph g,int v){int lowcost[MAXV];int min;int closest[MAXV];int i,j,k;for(i=0;i<g.vexnum;i++){lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.vexnum;i++){min=INF;for(j=0;j<g.vexnum;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("边(%d,%d)权为:%d\n",closest[k],k,min);lowcost[k]=0;for(j=0;j<g.vexnum;j++)if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}4、邻接矩阵的创建void CreatMGraph(MGraph &M){int n,e;cout<<"输入定点数:";cin>>n;M.vexnum=n;cout<<"输入弧数:";cin>>e;M.arcnum=e;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)M.edges[i][j]=0;elseM.edges[i][j]=INF;}}cout<<"输入边的权：（如1 2 3 表示点到点的权时）"<<endl;for(int i=0;i<2*e;i++){int x,y,z;cin>>x>>y>>z;M.edges[x][y]=z;}cout<<"输入点编号，名字："<<endl;for(int i=0;i<n;i++){int No;string str;cin>>No>>str;M.vexs[i].name=str;M.vexs[i].no=No;}}int const MAXV=16。
