最小生成树的应用.docx

武夷学院
课程设计报告
课程名称：
数据结构（C言语版本）
设计题目：
最小生成树的应用
学生班级：
10计科1班
学生姓名：
陈娟，谢贤根，黄伟伟，陈开槟
指导教师：
林丽惠
完成日期：
2012-01-05
小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]，采用邻接表作 为存储结构：
设置一个辅助数组：
lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前 最小权值；
closest域记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值 最小)。
用prim算法构造最小生成树的过程：
五、模块划分
预处理
#include <>
#include <>
#define inf 9999
#define max 40
#define linelenght 77
建立无向图
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) /*最大边数为 C 2，艮口 *n*(n-1)*/
{
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 */
输出无向图的邻接矩阵 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]);
}
}
}
void prim(int g[][max],int n)
{
int lowcost[max],closest[max];
int i,j,k,min;
for(i=2;i<=n;i++)
{ lowcost[i]=g[1][i];
closest[i]=1;
}
lowcost[1]=0;
for(i=2;i<=n;i++)
{
min=inf;
k=0;
for(j=2;j<=n;j++)
边，并把权值赋给min */
/* prim 函数 */
/*初始化*/
/*标志顶点1加入U集合*/
/*形成n-1条边的生成树*/
/*寻找权值最小的一条
printf("\n");
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])
{