#include <iostream>

#include <cmath>

#include <stdio.h>

#include <cstdio>

#include <cstring>

#include<algorithm>

#include<time.h>

#include<math.h>

#include <stdlib.h>

#include <string.h>

using namespace std;

#define MAX         100                 // 矩阵最大容量

#define INF         (~(0x1<<31))        // 最大值(即0X7FFFFFFF)

#define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))

#define LENGTH(a)   (sizeof(a)/sizeof(a[0]))

// 邻接矩阵

typedef struct _graph

{

    char vexs[MAX];       // 顶点集合

    int vexnum;           // 顶点数

    int edgnum;           // 边数

    int matrix[MAX][MAX]; // 邻接矩阵

}Graph, *PGraph;

// 边的结构体

typedef struct _EdgeData

{

    char start; // 边的起点

    char end;   // 边的终点

    int weight; // 边的权重

}EData;

/*

* 返回顶点ch在matrix矩阵中的位置

*/

static int get_position(Graph G, char ch)

{

    int i;

    for (i = ; i<G.vexnum; i++)

        if (G.vexs[i] == ch)

            return i;

    return -;

}

/*

* 创建图(用已提供的矩阵)

*/

Graph* create_example_graph()

{

    char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

    int matrix[][] = {

        /*A*//*B*//*C*//*D*//*E*//*F*//*G*/

        /*A*/{ ,  , INF, INF, INF,  ,   },

        /*B*/{ ,   ,  , INF, INF,   , INF },

        /*C*/{ INF,  ,   ,   ,   ,   , INF },

        /*D*/{ INF, INF,   ,   ,   , INF, INF },

        /*E*/{ INF, INF,   ,   ,   ,   ,    },

        /*F*/{ ,   ,   , INF,   ,   ,    },

        /*G*/{ , INF, INF, INF,   ,   ,    } };

    int vlen = LENGTH(vexs);

    int i, j;

    Graph* pG;

    // 输入"顶点数"和"边数"

    if ((pG = (Graph*)malloc(sizeof(Graph))) == NULL)

        return NULL;

    memset(pG, , sizeof(Graph));

    // 初始化"顶点数"

    pG->vexnum = vlen;

    // 初始化"顶点"

    for (i = ; i < pG->vexnum; i++)

        pG->vexs[i] = vexs[i];

    // 初始化"边"

    for (i = ; i < pG->vexnum; i++)

        for (j = ; j < pG->vexnum; j++)

            pG->matrix[i][j] = matrix[i][j];

    // 统计边的数目

    for (i = ; i < pG->vexnum; i++)

        for (j = ; j < pG->vexnum; j++)

            if (i != j && pG->matrix[i][j] != INF)

                pG->edgnum++;

    pG->edgnum /= ;

    return pG;

}

/*

* 获取图中的边

*/

EData* get_edges(Graph G)

{

    int i, j;

    int index = ;

    EData *edges;

    edges = (EData*)malloc(G.edgnum * sizeof(EData));

    for (i = ; i < G.vexnum; i++)

    {

        for (j = i + ; j < G.vexnum; j++)

        {

            if (G.matrix[i][j] != INF)

            {

                edges[index].start = G.vexs[i];

                edges[index].end = G.vexs[j];

                edges[index].weight = G.matrix[i][j];

                index++;

            }

        }

    }

    return edges;

}

/*

* 对边按照权值大小进行排序(由小到大)

*/

void sorted_edges(EData* edges, int elen)

{

    int i, j;

    for (i = ; i<elen; i++)

    {

        for (j = i + ; j<elen; j++)

        {

            if (edges[i].weight > edges[j].weight)

            {

                // 交换"第i条边"和"第j条边"

                EData tmp = edges[i];

                edges[i] = edges[j];

                edges[j] = tmp;

            }

        }

    }

}

/*

* 获取i的终点

*/

int get_end(int vends[], int i)

{

    while (vends[i] != )//如果当前顶点为0，则返回自己

        i = vends[i];

    return i;

}

/*

* 克鲁斯卡尔（Kruskal)最小生成树

*/

void kruskal(Graph G)

{

    int i, m, n, p1, p2;

    int length;

    int index = ;          // rets数组的索引

    int vends[MAX] = {  };     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。

    EData rets[MAX];        // 结果数组，保存kruskal最小生成树的边

    EData *edges;           // 图对应的所有边

                            // 获取"图中所有的边"

    edges = get_edges(G);

    // 将边按照"权"的大小进行排序(从小到大)

    sorted_edges(edges, G.edgnum);

    for (i = ; i<G.edgnum; i++)

    {

        p1 = get_position(G, edges[i].start);   // 获取第i条边的"起点"的序号

        p2 = get_position(G, edges[i].end);     // 获取第i条边的"终点"的序号

        m = get_end(vends, p1);                 // 获取p1在"已有的最小生成树"中的终点

        n = get_end(vends, p2);                 // 获取p2在"已有的最小生成树"中的终点

                                                // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路

        if (m != n)

        {

            vends[m] = n;                       // 设置m在"已有的最小生成树"中的终点为n

            rets[index++] = edges[i];           // 保存结果

        }

    }

    free(edges);

    // 统计并打印"kruskal最小生成树"的信息

    length = ;

    for (i = ; i < index; i++)

        length += rets[i].weight;

    printf("Kruskal=%d: ", length);

    for (i = ; i < index; i++)

        printf("(%c,%c) ", rets[i].start, rets[i].end);

    printf("\n");

}

int main()

{

    Graph* pG;

    // 自定义"图"(输入矩阵队列)

    //pG = create_graph();

    // 采用已有的"图"

    pG = create_example_graph();

    kruskal(*pG);             // kruskal算法生成最小生成树

    return ;

}