最小权语言问题●●算法题●●急需!!明天要!!
发布网友
发布时间：2022-04-29 09:08
共1个回答
热心网友
时间：2022-06-25 06:10
Prim算法的基本思想是：
(1) 在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U={v0}，集合T(E)为空。
(2) 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1 }，同时将该边加入集合T(E)中。
(3) 重复(2)，直到U = V为止。
这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树。
参考程序：
#include <stdio.h>
#define inf 9999
#define max 40
prim(int g[][max],int n)
{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");
}
}
int adjg(int g[][max]) //建立无向图
{int n,e,i,j,k,v1,v2,weight;
printf("输入顶点个数，边的条数：");
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("输入第%d条边的起点，终点，权值:",k);
scanf("%d,%d,%d",&v1,&v2,&weight);
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return(n);
}
void prg(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++)
printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);
}
printf("\n");
}
main()
{int g[max][max],n;
n=adjg(g);
printf("输入无向图的邻接矩阵:\n");
prg(g,n);
printf("最小生成树的构造:\n");
prim(g,n);
}
参考资料：http://zjc.ncu.cn/fws
