武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：09计科2班学生姓名：蒋家权，陈相财，吴继伟，梁丽春指导教师：林丽惠完成日期：2011-1-19课程设计项目研究报告目录一、问题分析和任务定义....................................................................................... - 1 -二、实现本程序需要解决的问题如下................................................................... - 1 -三、测试数据........................................................................................................... - 2 -四、算法思想........................................................................................................... - 3 -五、模块划分........................................................................................................... - 4 -六、算法设计与分析............................................................................................... - 7 -七、源程序............................................................................................................. - 11 -八、测试数据......................................................................................................... - 14 -九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 -十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。
求解如何以最低经济代价建设此通信网，这是一个最小生成树问题。
要求：（1）利用普利姆算法求网的最小生成树；（2）输出生成树中各边及权值。
二、实现本程序需要解决的问题如下(1)、如何选择存储结构去建立一个带权网络。
(2)、如何在所选存储结构下输出这个带权网络。
(3)、如何实现PRIM算法的功能。
(4)、如何从每个顶点开始找到所有的最小生成树的顶点。
(5)、如何输出最小生成树的边及其权值。
此问题的关键在于如何实现PRIM算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。
首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过PRIM的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设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 的最小生成树。
问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。
问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始省城的最小生成树。
题目要求以及达到目标：题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。
三、测试数据第一组顶点数（vertices）、边数（edge）：2、1起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、5 ，预测结果<1,2>5第二组顶点数（vertices）、边数（edge）：3、3起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、41、3、52、3、6预测结果<1,2>4、<1,3>5第三组顶点数（vertices）、边数（edge）：4、5 ，起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、31、3、41、4、62、4、73、4、5预测结果<1,2>3、<1,3>4、<1,4>6四、算法思想Prim算法求最小生成树的主要思想此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设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>#include <graphics.h>#define inf 9999#define max 40#define linelenght 77（2）普里姆算法void prim(int g[][max],int n) /* prim的函数*/{int lowcost[max],closest[max];int i,j,k,min;for(i=2;i<=n;i++) /* n个顶点，n-1条边*/ { lowcost[i]=g[1][i]; /* 初始化*/closest[i]=1; /* 顶点未加入到最小生成树中*/}lowcost[1]=0; /* 标志顶点1加入U集合*/ for(i=2;i<=n;i++) /* 形成n-1条边的生成树*/ {min=inf;k=0;for(j=2;j<=n;j++) /* 寻找满足边的一个顶点在U,另一个顶点在V的最小边*/if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",closest[k],k,min);lowcost[k]=0; /* 顶点k加入U */for(j=2;j<=n;j++) /* 修改由顶点k到其他顶点边的权值*/if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];closest[j]=k;}printf("\n");}}（3）输出分割线int priline(int h) /* 输出一条分割线*/{int g;printf("\n|");for(g=0;g<h;g++)printf("*");printf("|\n");}（4）提示错误信息int error() /* 提示错误信息*/{printf("\n\n|************************E*R*R*O*R************************|\ n");printf("Input errors or Data overflow please re-enter\n\n");fflush(stdin); /* 清除缓存*/}（5）建立无向图int adjg(int g[][max]) /* 建立无向图*/{int n,e,i,j,k,v1=0,v2=0,weight=0;printf("Input the number of vertices, number of the edge:");scanf("%d,%d",&n,&e);while(e<=0||e>=n*(n-1)||n>=max){error();printf("Input the number of vertices, number of the edge:");scanf("%d,%d",&n,&e);}for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=inf; /* 初始化矩阵，全部元素设为无穷大*/for(k=1;k<=e;k++){printf("Input the %d on the edge of the starting point, terminal, weights:",k);scanf("%d,%d,%d",&v1,&v2,&weight);while(v1==v2||v1>n||v2>n||v1<1||v2<1){error();printf("Input the %d on the edge of the starting point, terminal,weights:",k);scanf("%d,%d,%d",&v1,&v2,&weight);}g[v1][v2]=weight;g[v2][v1]=weight;}return(n);} /* 返回节点个数n */（6）输出无向图的邻接矩阵void pri(int g[][max],int n) /* 输出无向图的邻接矩阵*/ {int i,j;for(i=0;i<=n;i++)printf("%d\t",i);for(i=1;i<=n;i++){printf("\n%d\t",i);for(j=1;j<=n;j++) /* 输出边的权值*/{if(g[i][j]==inf) printf("%c\t",'\354');else printf("%d\t",g[i][j]);}}printf("\n");}（7）主函数模块void main() /* 主函数*/{int g[max][max],n;priline(linelenght);n=adjg(g);priline(linelenght);priline(linelenght);printf("Input the adjacency matrix without directed graph:\n");pri(g,n);printf("\n");printf("Minimum spanning tree structure:\n");prim(g,n);getch();}六、算法设计与分析（1）关于带权网络的存储形式要实现对于任意给定带权网络和顶点，运用PRIM基本算法思想求解所有的最小生成树的运算。
