文档介绍：安徽省巢湖学院信息工程学院
课程设计报告
课程名称《数据结构》
课题名称最小生成树问题
专业网络工程
班级
学号
姓名
联系方式
指导教师
2016年6月15日
目录
一、数据结构课程设计任务书
题目
设计要求
问题分析
功能和算法描述

基本思想
具体步骤
普利姆算法
基本思想
具体步骤
程序结构图
程序运行和数据显示
源程序代码
心得体会
《数据结构与算法》
课程设计报告

数据结构课程设计任务书
题目：最小生成树问题
设计要求：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
问题分析:
在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。
二、功能和算法描述：
系统有一个主界面,是选择界面。本系统一共有两种选择，克鲁斯卡尔算法求解和普利姆算法求解。根据提醒，输入相应数据，选择你想要的求解方式。第一种方式是克鲁斯卡尔算法。输入你想要建立网络的城市数量，然后输入它们两两之间的建设成本，运行得到网络的建立方式。第二种方式是普利姆算法，操作方法和第一种一致。
１．克鲁斯卡尔算法：
基本思想：
假设WN=（V, {E}）是一个含有N个顶点的连通网。则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有n-1条边为止。在此系统中，N是你所需要输入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设成本。
具体步骤：该算法的函数是main1( ) 。
先用 struct edgenode
{
int frontvex;
int rearvex;
int weight;
};
typedef edgenode adgeset[maxedgenum];
定义边结点，并定义一个此类结点的数组adgeset。Main1中先用scanf("%d",&n)语句得到建立网络的城市个数n。随后，通过insit1(adgeset&GT,int n)函数中的
for( i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{int x,y;x=i+1;y=j+1;
printf("请输入第%d个城市到第%d个城市的建设成本\n",x,y);
scanf("%d",&a);
GT[k].frontvex=i;
GT[k].rearvex=j;
GT[k].weight=a;
k++;
}
}
循环语句来得到每两个城市间的建设成本。
而后，通过
for(i=0;i<k-1;i++)
{
int min=20000,m=i;
for(int j=i;j<k;j++)
{
if(GT[j].weight<min)
{
min=GT[j].weight;
m=j;