数据结构与算法课程设计报告课程设计题目：最小生成树问题专业班级：信息与计算科学1001班姓名：谢炜学号：********* 设计室号：理学院机房设计时间： 2011-12-26 批阅时间：指导教师：杜洪波成绩：一、摘要：随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社会生活的重要组成部分。

我们希望拥有一个宽松的上网环境，以便更好的进行信息的交流，在此我们有必要提升我们的网络传播速度。

从某种程度上来说网络传播速度代表着一个国家网络化程度的高低。

为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。

而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。

通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。

在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。

于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。

在原来的基础上建立一个带有权值的网络图。

于是原有的问题就转化为找图的最小生成树问题。

我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。

二、问题分析在n个城市间建立通信网络，需架设n-1条路线。

求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。

我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。

将城市之间的距离当做网中各点之间的权值。

三、实现本程序需要解决的问题（1）如何选择存储结构去建立一个带权的网络；（2）如何在所选存储结构下输出这个带权网络；（3）如何实现普利姆算法的功能；（4）如何从每个顶点开始找到所有的最小生成树的顶点；（5）如何输出最小生成树的边及其权值此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。

现在我们问题做如下的分析：这个问题主要在于普利姆算法的实现。

我们将各个城市的空间分布抽象成一个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的各个顶点。

我们建立的输入的数据格式为：首先提示输入带权的顶点数目，我定义为整形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整数类型数据，这样我们就建立了一个带权的网络。

问题的输出我是将我们所得到的最小生成树的路线输出出来。

题目的要求就是我们在n个城市之间架设网络得到的最为经济的架设方法，我们进行以上的工作就是在找我们所需要的最小生成树，已解决我们的问题。

四、算法思想普利姆算法求最小生成树的主要思想假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。

算法从U={u0}( u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。

此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。

对于最小生成树问题：最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个但是他们权值之和是相等的。

五、程序设计流程图：六、模块划分（1）预处理#include<stdio.h>#define maxvertexnum 20#define maxedgenum 40typedef int adjmatrix[maxvertexnum][maxvertexnum];（2）定义一个储存节点信息的结构体struct edgenode{int frontvex;int rearvex;int weight;};typedef edgenode adgeset[maxedgenum];（3）初始化的无向图，将每条边的权值赋值为无穷void insitadj(adjmatrix &GA){for(int i=1;i<maxvertexnum;i++){for(int j=1;j<maxvertexnum;j++){GA[i][j]=20000; //将边的权值赋值为无穷// }}}（4）以各个城市为基础建立一个网络void setadj(adjmatrix &GA,int n) //建立网络{for(int i=1;i<=n+1;i++){for(int j=i+1;j<n+1;j++){printf("请输入第%d个城市到第%d个城市的距离：",i,j);scanf("%d",&GA[i][j]);}}for(i=1;i<=n+1;i++){for(int j=i+1;j<n+1;j++){GA[j][i]=GA[i][j];}}}（5）将建立的网络各个连接的节点赋上权值void insit(adgeset&GT,int n,adjmatrix GA){for(int i=1;i<n;i++){GT[i].frontvex=1;GT[i].rearvex=i+1;GT[i].weight=GA[1][i+1];}（6）输出我们所找到的最小生成树void fun(adjmatrix GA,adgeset&GT,int n){ int i;for(i=1;i<n;i++){int min=10000,m=i;for(int j=i;j<n;j++){if(GT[j].weight<min){min=GT[j].weight;m=j;}}edgenode temp=GT[i];GT[i]=GT[m];GT[m]=temp;int k=GT[m].rearvex;for(j=i;j<n;j++){int t=GT[j].rearvex;int w=GA[k][t];if(w<GT[j].weight){GT[j].weight=w;GT[j].frontvex=k;}}}}void display(adgeset GT,int n){for(int i=1;i<n;i++){printf("第%d个城市到第%d城市修建一条电缆!\n",GT[i].frontvex,GT[i].rearvex);}printf("这样修建可以使距离最短！");}（7）主函数int main()printf("请问您要在几个城市间建立网络？\n请在此输入：");int n;scanf("%d",&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;}七、算法设计与分析选定存储形式要实现对于给定带权网络和顶点，运用普利姆基本算法思想求解所有的最小生成树的运算，在这里我们首先要明确所选用的数据结构，即采用何种数据结构来存储带权网络，这是必须首先解决的问题，我们采用图的邻接矩阵的存储方式来存储带权网络。

我们在建立邻接矩阵的时候选用数组来分别存储每个节点的信息以及边的权值。

八、源程序#include<stdio.h>#define maxvertexnum 20#define maxedgenum 40typedef int adjmatrix[maxvertexnum][maxvertexnum];struct edgenode{int frontvex;int rearvex;int weight;};typedef edgenode adgeset[maxedgenum];//===============================================void insitadj(adjmatrix &GA);void setadj(adjmatrix &GA,int n);void fun(adjmatrix GA,adgeset &GT,int n);void display(adgeset GT,int n);void insit(adgeset &GT,int n,adjmatrix GA);//=============================================void insit(adgeset&GT,int n,adjmatrix GA){for(int i=1;i<n;i++){GT[i].frontvex=1;GT[i].rearvex=i+1;GT[i].weight=GA[1][i+1];}}void insitadj(adjmatrix &GA){for(int i=1;i<maxvertexnum;i++){for(int j=1;j<maxvertexnum;j++){GA[i][j]=20000;}}}void setadj(adjmatrix &GA,int n) //建立网络{for(int i=1;i<=n+1;i++){for(int j=i+1;j<n+1;j++){printf("请输入第%d个城市到第%d个城市的距离：",i,j);scanf("%d",&GA[i][j]);}}for(i=1;i<=n+1;i++){for(int j=i+1;j<n+1;j++){GA[j][i]=GA[i][j];}}}void fun(adjmatrix GA,adgeset&GT,int n){ int i;for(i=1;i<n;i++){int min=10000,m=i;for(int j=i;j<n;j++){if(GT[j].weight<min){min=GT[j].weight;m=j;}}edgenode temp=GT[i];GT[i]=GT[m];GT[m]=temp;int k=GT[m].rearvex;for(j=i;j<n;j++){int t=GT[j].rearvex;int w=GA[k][t];if(w<GT[j].weight){GT[j].weight=w;GT[j].frontvex=k;}}}}void display(adgeset GT,int n){for(int i=1;i<n;i++){printf("第%d个城市到第%d城市修建一条电缆!\n",GT[i].frontvex,GT[i].rearvex);}printf("这样修建可以使距离最短！");}int main(){printf("请问您要在几个城市间建立网络？\n请在此输入：");int n;scanf("%d",&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;}九、算法实现（1）提示输入截图(2)输入各节点间的权（3）输出结果十、心得体会数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。