该楼层疑似违规已被系统折叠隐藏此楼查看此楼
#include
#include
#include
#define INFINITY 30000//权值最大值
#define max_vertex_num 20//最大顶点数
typedef struct{
int arcs[max_vertex_num][max_vertex_num]; //邻接矩阵
int vexnum,arnum;//图当前的顶点和边数
}Graph;
typedef struct{
int adjvex;//某顶点与已构造好部分生成树的顶点之间权值最小的顶点
int lowcost;//某顶点与已构造好部分生成树的顶点之间的最小权值
}ClosEdge;//用prim算法求最小生成树的辅助数组
void CreateGraph(Graph g)//生成邻接矩阵
{
int i,j;
int start,end,weight;
for(i=1;i<=g.vexnum;i++)
for(j=1;j<=g.vexnum;j++)
g.arcs[i][j]=INFINITY;//矩阵初始化
printf("输入每条边的两个关联顶点编号和其权值：\n");
for(i=1;i<=g.arnum;i++)
{
scanf("%d %d %d",&start,&end,&weight);
g.arcs[start][end]=weight;
g.arcs[end][start]=weight;
}
}
int minimun(ClosEdge cl[],int vnum)//在辅助数组中选择权值最小的顶点并返回其位置
{
int i;
int w,p;
w=INFINITY;
for(i=1;i<=vnum;i++)
{
if(cl[i].lowcost!=0&&cl[i].lowcost
{
w=cl[i].lowcost;
p=i;
}
}
return p;
}
void MiniSpanTree_PRIM(Graph g,int u)
{
ClosEdge closedge[max_vertex_num];
int i,j,k;
printf("最小生成树:\n");
for(j=1;j<=g.vexnum;j++)//辅助数组初始化
{
if(j!=u)
{
closedge[j].adjvex=u;
closedge[j].lowcost=g.arcs[u][j];
}
}
closedge[u].lowcost=0;//初始，U={u} ；
for(i=1;i
{
k=minimun(closedge,g.vexnum);//求生成树的下一个顶点
printf("%d %d\n",closedge[k].adjvex,k);
closedge[k].lowcost=0;//第k个顶点并入U集
for(j=1;j<=g.vexnum;j++)//新顶点并入后重新选择最小边
{
if(g.arcs[k][j]
{
closedge[j].adjvex=k;
closedge[j].lowcost=g.arcs[k][j];
}
}
}
}
int main()
{
Graph g;
char jx='y';
int u;
while(jx!='N'&&jx!='n')
{
printf("请输入图的顶点和边数:\n");
scanf("%d %d",&g.vexnum,&g.arnum);
CreateGraph(g);
printf("请输入构造最小生成树的开始顶点:\n");
scanf("%d",&u);
MiniSpanTree_PRIM(g,u);
printf("最小生成树构造完毕，继续进行吗?\n");
scanf("%c",&jx);
}
return 0;
}
