#include <stdio.h>
#define MAX_VERTEX_NUM 10
#define INFINITY 1000

typedef struct Edge
{
int weight;
}Edge, EdgeMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph
{
EdgeMatrix edges;
int vexnum;
int edgenum;
}MGraph;

typedef struct
{
int vertex;
int lowcost;
}Closedge;

void InitializeMG(MGraph &G)
{
G.edgenum = G.vexnum = 0;
for(int i = 0; i < MAX_VERTEX_NUM; ++i)
for(int j = 0; j < MAX_VERTEX_NUM; ++j)
G.edges[i][j].weight = INFINITY;
}

void CreateGraph(MGraph &G)
{
int i, j;
G.vexnum = 6;
G.edgenum = 10;

G.edges[0][1].weight = G.edges[1][0].weight = 6;
G.edges[0][2].weight = G.edges[2][0].weight = 1;
G.edges[0][3].weight = G.edges[3][0].weight = 5;
G.edges[1][2].weight = G.edges[2][1].weight = 5;
G.edges[1][4].weight = G.edges[4][1].weight = 3;
G.edges[2][3].weight = G.edges[3][2].weight = 5;
G.edges[2][4].weight = G.edges[4][2].weight = 6;
G.edges[2][5].weight = G.edges[5][2].weight = 4;
G.edges[3][5].weight = G.edges[5][3].weight = 2;
G.edges[4][5].weight = G.edges[5][4].weight = 6;

printf("\tv1\tv2\tv3\tv4\tv5\tv6\n");
for(i = 0; i < G.vexnum; ++i)
{
printf("\n\nv%d\t", i+1);
for(j = 0; j < G.vexnum; ++j)
printf("%d\t", G.edges[i][j].weight);
}
}

int GetMinIndex(MGraph G, Closedge closedge[])
{
int i, min_index = -1, min = INFINITY;
for(i = 1; i < G.vexnum; ++i)
if(closedge[i].lowcost && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
min_index = i;
}

return min_index;
}

bool MiniSpanTree_Prim(MGraph G, Closedge closedge[], int v0)
{
int i, j, k;
for(i = 0; i < G.vexnum; ++i)
{
closedge[i].vertex = v0;
closedge[i].lowcost = G.edges[v0][i].weight;
}
closedge[v0].lowcost = 0;

printf("\n\nThe Minimal-Span-Tree is composed of following edges:\nedge\t\tWeight\n");
for(i = 1; i < G.vexnum; ++i)
{
k = GetMinIndex(G, closedge);
if(k == -1)
return false;
printf("<%d, %d>\t\t%d\n",
closedge[k].vertex, k, closedge[k].lowcost);
closedge[k].lowcost = 0;
for(j = 0; j < G.vexnum; ++j)
if(G.edges[k][j].weight < closedge[j].lowcost)
{
closedge[j].vertex = k;
closedge[j].lowcost = G.edges[k][j].weight;
}
}
return true;
}

void main()
{
MGraph G;
Closedge closedge[6];