#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define MAXCOST 9999
typedef struct vertex
{
int num;
int weight;
} vertex;
typedef struct
{
vertex vers[MAX+1];
int edges[MAX+1][MAX+1];
int n,e;
} MGraph;
typedef struct
{
int fromvex,endvex;
int weight;
} Edge,Edgeset[MAX+1];
Edgeset GE;
void Creat(MGraph *g,int n,int e)
{
int i,j,k,v1,v2;
g->n=n;
g->e=e;
for(i=1; i<=g->n; i++)
g->vers[i].num=i;
for(i=1; i<=g->n; i++)
for(j=1; j<=g->n; j++)
g->edges[i][j]=0;
printf("\n请输入权值 and 所对应的两条边的节点的下标:\n") ;
for(k=1; k<=g->e; k++)
{
scanf("%d",&g->vers[k].weight);
scanf("%d%d",&v1,&v2);
g->edges[v1][v2]=g->vers[k].weight;
g->edges[v2][v1]=g->vers[k].weight;
}
}
void Prim(MGraph *g)
{
int i,j,k,mincost;
int lowcost[MAX+1];
int closevertex[MAX+1];
for(i=1; i<=g->n; i++)
{
if(i==1)
lowcost[i]=0;
else
lowcost[i]=g->edges[1][i];
closevertex[i]=1;
}
for(i=1; i<g->n; i++)
{
mincost=MAXCOST;
k=1;
for(j=2; j<=g->n; j++)
if(lowcost[j]!=0&&lowcost[j]<mincost)
{
mincost=lowcost[j];
k=j;
}
if(mincost==MAXCOST)
{
printf("图不连通,无生成树!");
return ;
}
printf("(%d,%d,%d)\n",closevertex[k],k,lowcost[k]);
lowcost[k]=0;
for(j=1; j<=g->n; j++)
{
if(lowcost[j]!=0&&g->edges[k][j]<lowcost[j])
{
closevertex[j]=k;
lowcost[j]=g->edges[k][j];
}
}
}
}
/*
void CreatGE(MGraph *g,Edgeset GE)
{
int i,j;
Edge temp;
int k=1;
for(i=1; i<=g->n; i++)
for(j=1; j<i; j++)
if(g->edges[i][j]!=MAXCOST)
{
GE[k].weight=g->edges[i][j];
GE[k].fromvex=i;
GE[k].endvex=j;
k++;
}
for(i=1; i<=g->e; i++)
for(j=1; j<g->e; j++)
if(GE[j].weight>GE[j+1].weight)
{
temp=GE[j];
GE[j]=GE[j+1];
GE[j+1]=temp;
}
}
void Kruskal(MGraph g,Edgeset GE,Edgeset TE)
{
int vest[MAX],i,j,k,d,m1,m2;
for(i=1;i<=g.n;i++)
vest[i]=i;
for(d=1,k=1;k<g.n;i++)
{
m1=vest[GE[d].fromvex];
m2=vest[GE[d].endvex];
if(m1!=m2)
{
TE[k]=GE[d];
k++;
for(j=1;j<=g.n;j++)
{
if(vest[j]=m2)
vest[j]=m1;
}
}
}
}
*/
int main()
{
MGraph *g;
int n,e;
g=(MGraph*)malloc(sizeof(MGraph));
printf("请输入顶点数和边数:");
scanf("%d%d",&n,&e);
Creat(g,n,e);
Prim(g);
return 0;
}
