大话数据结构--Kruskal算法

7.5.3Kruskal算法

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题

②把求解的问题分成若干个子问题

③对每个子问题求解，得到子问题的局部最优解

④把子问题的解局部最优解合成原来解问题的一个解

克鲁斯卡尔算法（Kruskal）是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。

第一步：将图中所有的边按照权值进行非降序排列；

第二步：从图中所有的边中选择可以构成最小生成树的边。

0. 选择权值最小的边 ：没有环形成，则添加：
1. 

2. 选择边 ：没有形成环，则添加：
3. 
   

3. 选择边 ：没有形成环，则添加：
4. 

4. 选择边 ：没有形成环，则添加：
5. 

5. 选择边 ：没有形成环，则添加：
6. 

6. 选择边 ：没有形成环，则添加：
7. 

7. 选择边 ：没有形成环，则添加：

8. 选择边 ：添加这条边将导致形成环，舍弃，不添加；
9. 选择边 ：添加这条边将导致形成环，舍弃，不添加；
10. 选择边 ：没有形成环，则添加：

此时已经包含了图中顶点个数9减1条边，算法停止。

下面我们来用代码实现

int Find(int *parent, int f)
 {
  while( parent[f] > 0 )
  {
   f = parent[f];
  }
  return f;
 }
 // Kruskal算法生成最小生成树
 void MiniSpanTree_Kruskal(MGraph G)
 {
  int i, n, m;
  Edge edges[MAGEDGE]; // 定义边集数组
  int parent[MAXVEX];  // 定义parent数组用来判断边与边是否形成环路
  int eCount = 0;
  for( i=0; i < G.numVertexes; i++ )
  {
   parent[i] = 0;
  }
  for( i=0; i < G.numEdges; i++ )
  {
   n = Find(parent, edges[i].begin); // 4 2 0 1 5 3 8 6 6 6 7
   m = Find(parent, edges[i].end);  // 7 8 1 5 8 7 6 6 6 7 7
   if( n != m )  // 如果n==m，则形成环路，不满足！
   {
    parent[n] = m; // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
    printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
    ++eCount;
    if( eCount == (G.numVertexes-1)){
     break;
    }
   }
  }
 }

时间复杂度分析

O(ElogE)或者O(ElogV)，其中E代表图中的边的数目，V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环，判断添加一条边是否构成环最坏情况下需要O(logV)，关于这个复杂度等到景禹给你们谈并查集的时候再分析；因此，总的时间复杂度为O(ElogE + ElogV)，其中E的值最大为V(V-1)/2，因此O(logV) 等于 O(logE)。因此，总的时间复杂度为O(ElogE) 或者O(ElogV)。