#define USED 0
#define NOADJ -1
void Prim(MatrixGraph G)
{
int i,j,k,min,sum = 0;
int weight[VERTEX_MAX];
char tmpvertex[VERTEX_MAX];
for(i=1;i<G.VertexNum;i++)
{
weight[i] = G.Edges[0][i];
if(weight[i] == MAXVALUE)
tmpvertex[i] = NOADJ;
else
tmpvertex[i] = G.Vertex[0];
}
tmpvertex[0] = USED;
weight[0] = MAXVALUE;
for(i=1;i<G.VertexNum;i++)
{
min = weight[0];
k = i;
for(j=1;j<G.VertexNum;j++)
if(weight[j] < min && tmpvertex[j] != 0)
{
min = weight[j];
k = j;
}
sum += min;
printf("(%c,%c),",tmpvertex[k],G.Vertex[k]);
tmpvertex[k] = USED;
weight[k] = MAXVALUE;
for(j=0;j<G.VertexNum;j++)
if(G.Edges[k][j] < weight[j] && tmpvertex[j] != 0)
{
weight[j] = G.Edges[k][j];
tmpvertex[j] = G.Vertex[k];
}
}
printf("\n min tree %d\n",sum);
}
