#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 VexGroup
{
    int vertex;
    int group;
}VexGroup;

typedef struct EdgeMuster
{
    int  tail;
    int  head;
    int  weight;
    bool used;
}EdgeMuster;

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);
    }
}

void InitializeEVG(MGraph G, EdgeMuster E[], VexGroup VG[])
{
    int i, j, k = 0;
    for(i = 0; i < G.vexnum; ++i)
    {
        VG[i].vertex = VG[i].group = i;
        for(j = 0; j < i; ++j)
            if(G.edges[i][j].weight != INFINITY)
            {
                E[k].head   = j;
                E[k].tail   = i;
                E[k].weight = G.edges[i][j].weight;
                E[k++].used   = false;
            }
    }
}

int GetMinIndex(MGraph G, EdgeMuster E[], VexGroup VG[])
{
    int i, min_index = -1, min = INFINITY;
    for(i = 0; i < G.edgenum; ++i)
    {
        if(!E[i].used 
            && VG[E[i].head].group != VG[E[i].tail].group
            && E[i].weight < min)
        {
            min_index = i;
            min = E[i].weight;
        }
    }
    return min_index;
}

void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, k;
    EdgeMuster *E = new EdgeMuster[G.edgenum];
    VexGroup  *VG = new VexGroup[G.vexnum];
    InitializeEVG(G, E, VG);

    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, E, VG);
        E[k].used = true;
        for(j = 0; j < G.vexnum; ++j)
        {
            if(VG[j].group == VG[E[k].head].group)
                VG[j].group = VG[E[k].tail].group;
        }
        printf("<%d, %d>\t\t%d\n", E[k].tail, E[k].head, E[k].weight);
    }
}

void main()
{
    MGraph  G;
    InitializeMG(G);
    CreateGraph(G);
    MiniSpanTree_Kruskal(G);
}