# include <stdio.h>

 # define MAX_VERTEXES //最大顶点数

 # define MAXEDGE //边集数组最大值

 # define INFINITY //代表不可能的数（无穷大）

 typedef struct

 {//图 结构体定义

     int arc[MAX_VERTEXES][MAX_VERTEXES];//二位数组 矩阵

     int numVertexes, numEdges;//当前图中的顶点数和边数

 }MGraph;

 typedef struct

 {//边集数组 结构体定义

     int begin;

     int end;

     int weight;

 }Edge;

 void CreateMGraph (MGraph *G)

 {//创建

      int i, j;

      //下面是已经输入好的

      G->numVertexes = ;

      G->numEdges = ;

      for (i=; i<G->numVertexes; i++)

          for (j=; j<G->numVertexes; j++)

              if (i == j)

                  G->arc[i][j] = ;

              else

                  G->arc[i][j] = G->arc[j][i] = INFINITY;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=; 

     for (i=; i<G->numVertexes; i++)

         for (j=i+; j<G->numVertexes; j++)//矩阵的上三角，然后对称矩阵的下三角

             G->arc[j][i]  = G->arc[i][j];//对称

 }

 void swapn (Edge *edges, int i, int j)

 {//交换权值

     int temp;

     //起始

     temp = edges[i].begin;

     edges[i].begin = edges[j].begin;

     edges[j].begin = temp;

     //结束

     temp = edges[i].end;

     edges[i].end = edges[j].end;

     edges[j].end = temp;

     //权值

     temp = edges[i].weight;

     edges[i].weight = edges[j].weight;

     edges[j].weight = temp;

     return ;

 }

 void sort (Edge edges[], MGraph *G)

 {//对权值进行排序

     int i, j;

     for (i=; i<G->numEdges; i++)

         for (j=i+; j<G->numEdges; j++)//对存入有效边(两端点的权值)进行冒泡排序

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

                 swapn (edges, i, j);//交换权值

     printf ("排序过后：\n");

     for (i=; i<G->numEdges; i++)

         printf ("边：(%d,%d) 权值：%d\n", edges[i].begin, edges[i].end, edges[i].weight);

     return ;

 }

 int Find (int *parent, int f)//★

 {// 查找连线顶点的尾部下标

 //走过的路都有记录，如果走已经走过的路的话，那么返回的值(n=m);

     while (parent[f] > )

         f = parent[f];

     return f;

 }

 void MiniSpanTree_Kruskal (MGraph G)

 {//克鲁斯卡尔算法

     int i, j, n, m;

     int k = ;

     int parent[MAX_VERTEXES];//定义一维数组判断是否形成环路

     Edge edges[MAXEDGE];//定义边集数组

     for (i=; i<G.numVertexes; i++)//存储有效的边(两个端点和权值)

         for (j=i+; j<G.numVertexes; j++)//矩阵上三角进行比较，因为对称，所以比较一半更节约时间

             if (G.arc[i][j] < INFINITY)

             {

                 edges[k].begin = i;

                 edges[k].end = j;

                 edges[k ++].weight = G.arc[i][j];

             }

     sort(edges, &G);//排序

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

         parent[i] = ;

     printf ("\n打印最小生成树：\n");

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

     {

         n = Find (parent, edges[i].begin);//★

         m = Find (parent, edges[i].end);//★

         if (n != m)

         {

             parent[n] = m;

             printf ("边(%d,%d) 权值：%d\n", edges[i].begin, edges[i].end, edges[i].weight);

         }

     }

 }

 int main (void)

 {

     MGraph G;

     CreateMGraph (&G);//创建

     MiniSpanTree_Kruskal (G);//克鲁斯卡尔 算法

     return ;

 }

 /*

 在vc++6.0运行结果：

     排序过后：

     边：(4,7) 权值：7

     边：(2,8) 权值：8

     边：(0,1) 权值：10

     边：(0,5) 权值：11

     边：(1,8) 权值：12

     边：(3,7) 权值：16

     边：(1,6) 权值：16

     边：(5,6) 权值：17

     边：(1,2) 权值：18

     边：(6,7) 权值：19

     边：(3,4) 权值：20

     边：(3,8) 权值：21

     边：(2,3) 权值：22

     边：(3,6) 权值：24

     边：(4,5) 权值：26

     打印最小生成树：

     边(4,7) 权值：7

     边(2,8) 权值：8

     边(0,1) 权值：10

     边(0,5) 权值：11

     边(1,8) 权值：12

     边(3,7) 权值：16

     边(1,6) 权值：16

     边(6,7) 权值：19

     Press any key to continue

 */