文字描述

　　上一篇博客介绍了最小生成树(普里姆算法)，知道了普里姆算法求最小生成树的时间复杂度为n^2, 就是说复杂度与顶点数无关，而与弧的数量没有关系；

　　而用克鲁斯卡尔(Kruskal)算法求最小生成树则恰恰相反。它的时间复杂度为eloge (e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

　　克鲁斯卡尔算法求最小生成树的步骤为：假设连通网N={V,{E}}, 则令最小生成树的初始状态为只有n个顶点而无边的非连通图 T=(V, {}}, 图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量中，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。

 

示意图：

 

算法分析：

　　实现克鲁斯卡尔的话，可以借助于之前介绍的”堆”(堆排序)和树的等价划分的方法。用”堆”来存放网中的边，则每次选择最小代价的边仅需loge的时间(第一次需e)。又生成树T的每个连通分量可看成一个等价类，则构造T加入新的边的过程类似于求等价类的过程，由此可用MFSet类型来描述顶点，用堆Heap存放弧结点信息，使构造T的过程仅需eloge的时间，由此，克鲁斯

 

代码实现

  1.   1 //
  2.   2 // Created by lady on 18-12-15.
  3.   3 //
  4.   4 
  5.   5 #include <stdio.h>
  6.   6 #include <stdlib.h>
  7.   7 #include <string.h>
  8.   8 
  9.   9 #define MAX_NODE_NUM 20
  10.  10 #define MAX_ARCH_NUM 30
  11.  11 
  12.  12 #define EQ(a, b) ((a)==(b))
  13.  13 #define LT(a, b) ((a) <(b))
  14.  14 #define LQ(a, b) ((a)<=(b))
  15.  15 
  16.  16 
  17.  17 typedef struct PTNode{
  18.  18     char data[10];
  19.  19     int index;
  20.  20     int parent;
  21.  21 }PTNode;
  22.  22 
  23.  23 typedef struct{
  24.  24     PTNode node[MAX_NODE_NUM+1];
  25.  25     int n;
  26.  26 }MFSet;
  27.  27 
  28.  28 typedef struct ArcBox{
  29.  29     int vex1, vex2;
  30.  30     int weight;
  31.  31 }ArcBox;
  32.  32 
  33.  33 typedef  struct{
  34.  34     ArcBox r[MAX_ARCH_NUM+1];
  35.  35     int len;
  36.  36 }HeapType;
  37.  37 
  38.  38 /* param1 S: S是已存在的集合
  39.  39  * param2 index: index是S中某个子集的成员的下标值
  40.  40  * result: 查找函数，确定S中位置为index所属子集Si，并返回其子集中的根结点的位置。
  41.  41  */
  42.  42 static int findMFSet(MFSet *S, int index)
  43.  43 {
  44.  44     if(index < 1 || index > S->n)
  45.  45         return -1;
  46.  46     int j = 0;
  47.  47     for(j=index; S->node[j].parent>0; j=S->node[j].parent);
  48.  48     return j;
  49.  49 }
  50.  50 
  51.  51 /*
  52.  52  * 集合S中位置为index_i和index_j所在的子集互不相交。
  53.  53  * result: 将置为index_i和index_j所在的互不相交的子集合并为一个子集。
  54.  54  */
  55.  55 static int mergeMFSet(MFSet *S, int index_i, int index_j)
  56.  56 {
  57.  57     int loc_i = -1, loc_j = -1;
  58.  58     if((loc_i=findMFSet(S, index_i)) < 0){
  59.  59         return -1;
  60.  60     }
  61.  61     if((loc_j=findMFSet(S, index_j)) < 0){
  62.  62         return -1;
  63.  63     }
  64.  64     if(loc_i == loc_j){
  65.  65         return -1;
  66.  66     }
  67.  67     //结点数少的子集指向结点数大的子集
  68.  68     if(S->node[loc_i].parent > S->node[loc_j].parent){
  69.  69         S->node[loc_j].parent += S->node[loc_i].parent;
  70.  70         S->node[loc_i].parent = loc_j;
  71.  71     }else{
  72.  72         S->node[loc_i].parent += S->node[loc_j].parent;
  73.  73         S->node[loc_j].parent = loc_i;
  74.  74     }
  75.  75     return 0;
  76.  76 }
  77.  77 
  78.  78 static int initialMFSet(MFSet *S, int n)
  79.  79 {
  80.  80     int i = 0;
  81.  81     S->n = n;
  82.  82     for(i=1; i<=S->n; i++)
  83.  83     {
  84.  84         printf("输入第%d个子集:", i);
  85.  85         scanf("%s", S->node[i].data);
  86.  86         S->node[i].parent = -1;
  87.  87         S->node[i].index = i;
  88.  88     }
  89.  89     return 0;
  90.  90 }
  91.  91 
  92.  92 /*
  93.  93  * 返回结点中数据等于data的下标值
  94.  94  */
  95.  95 static int getLocaofVex(MFSet *S, char data[])
  96.  96 {
  97.  97     int i = 0;
  98.  98     for(i=1; i<=S->n; i++){
  99.  99         if(!strncasecmp(S->node[i].data, data, sizeof(S->node[0].data))){
  100. 100             return S->node[i].index;
  101. 101         }
  102. 102     }
  103. 103     return -1;
  104. 104 }
  105. 105 
  106. 106 static void printMFSet(MFSet *S)
  107. 107 {
  108. 108     printf("打印MFSet结构中的数据:\n");
  109. 109     int i = 0;
  110. 110     for(i=1; i<=S->n; i++){
  111. 111         printf("index %d:(data %s, parent %d)\n", S->node[i].index, S->node[i].data, S->node[i].parent);
  112. 112     }
  113. 113     printf("\n");
  114. 114 }
  115. 115 
  116. 116 
  117. 117 
  118. 118 //////////////////////////////////////////////
  119. 119 
  120. 120 static int printHeap(HeapType *H)
  121. 121 {
  122. 122     printf("打印堆结构中的数据:\n");
  123. 123     int i = 0;
  124. 124     for(i=1; i<=H->len; i++){
  125. 125         printf("index %d: arch:(%d,%d),weight %d)\n", i, H->r[i].vex1, H->r[i].vex2, H->r[i].weight);
  126. 126     }
  127. 127     return 0;
  128. 128 }
  129. 129 
  130. 130 static int initialHeap(HeapType *H, MFSet *S, int n)
  131. 131 {
  132. 132     H->len = n;
  133. 133     int i = 0;
  134. 134     char s1[10] = {0};
  135. 135     char s2[10] = {0};
  136. 136     char s3[10] = {0};
  137. 137     int weight = 0;
  138. 138 
  139. 139     char tmp[30] = {0};
  140. 140     for(i=1; i<=H->len; i++)
  141. 141     {
  142. 142         printf("输入第%d条弧信息(顶点1 顶点2 权值)：", i);
  143. 143         memset(tmp, 0, sizeof(tmp));
  144. 144         scanf("%s", tmp);
  145. 145         sscanf(tmp, "%[^\',\'],%[^\',\'],%s[^\\n]", s1, s2, s3);
  146. 146         H->r[i].vex1 = getLocaofVex(S, s1);
  147. 147         H->r[i].vex2 = getLocaofVex(S, s2);
  148. 148         H->r[i].weight = atoi(s3);
  149. 149     }
  150. 150     return 0;
  151. 151 }
  152. 152 
  153. 153 /*
  154. 154  *已知H->r[s,...,m]中记录的关键字除H->r[s].key之外均满足的定义
  155. 155  *本函数调整H-r[s]的关键字，使H->r[s,...,m]成为一个小顶堆(对其中
  156. 156  *记录的弧的权值而言)
  157. 157  */
  158. 158 void HeapAdjust(HeapType *H, int s, int m)
  159. 159 {
  160. 160     ArcBox rc = H->r[s];
  161. 161     int j = 0;
  162. 162     //沿weight较小的孩子结点向下筛选
  163. 163     for(j=2*s; j<=m; j*=2){
  164. 164         //j为weight较小的孩子结点下标
  165. 165         if(j<m && (!LQ(H->r[j].weight, H->r[j+1].weight)))
  166. 166             j+=1;
  167. 167         if(LQ(rc.weight, H->r[j].weight))
  168. 168             break;
  169. 169         H->r[s] = H->r[j];
  170. 170         s=j;
  171. 171     }
  172. 172     H->r[s] = rc;
  173. 173 }
  174. 174 
  175. 175 void HeapSort(HeapType *H, MFSet *S)
  176. 176 {
  177. 177     int i = 0;
  178. 178     printf("1)建立一个小顶堆!\n");
  179. 179     //把H->r[1,...,H->length]建成小顶堆
  180. 180     for(i=H->len/2; i>=1; i--){
  181. 181         HeapAdjust(H, i, H->len);
  182. 182     }
  183. 183     printHeap(H);
  184. 184     printf("2)依次输出堆顶元素并重新调整成小顶堆!\n");
  185. 185     ArcBox tmp;
  186. 186     for(i=H->len; i>1; i--){
  187. 187         tmp = H->r[1];
  188. 188         H->r[1] = H->r[i];
  189. 189         H->r[i] = tmp;
  190. 190         HeapAdjust(H, 1, i-1);
  191. 191         printf("新堆顶的弧信息: (%d,%d) %d", tmp.vex1, tmp.vex2, tmp.weight);
  192. 192         if(mergeMFSet(S, tmp.vex1, tmp.vex2) > -1){
  193. 193             printf("\t是最小生成树的弧!\n");
  194. 194         }else{
  195. 195             printf("\n");
  196. 196         }
  197. 197     }
  198. 198 }
  199. 199 
  200. 200 
  201. 201 
  202. 202 
  203. 203 int main(int argc, char *argv[])
  204. 204 {
  205. 205     int nodes=0;
  206. 206     int archs=0;
  207. 207     printf("输入顶点数和弧数:");
  208. 208     scanf("%d,%d", &nodes, &archs);
  209. 209 
  210. 210     printf("\n以MFSet结构存放顶点信息:\n");
  211. 211     MFSet S;
  212. 212     initialMFSet(&S, nodes);
  213. 213     printMFSet(&S);
  214. 214 
  215. 215     printf("以堆结构存放弧信息:\n");
  216. 216     HeapType H;
  217. 217     initialHeap(&H, &S, archs);
  218. 218     printHeap(&H);
  219. 219 
  220. 220     printf("对存放了弧信息的堆进行排序,在排序过程中输入最小生成树的边\n");
  221. 221     HeapSort(&H, &S);
  222. 222     return 0;
  223. 223 }

最小生成树(克鲁斯卡尔算法)

 

代码运行

  1. /home/lady/CLionProjects/untitled/cmake-build-debug/untitled
  2. 输入顶点数和弧数:6,10
  4. 以MFSet结构存放顶点信息:
  5. 输入第1个子集:V1
  6. 输入第2个子集:V2
  7. 输入第3个子集:V3
  8. 输入第4个子集:V4
  9. 输入第5个子集:V5
  10. 输入第6个子集:V6
  11. 打印MFSet结构中的数据:
  12. index 1:(data V1, parent -1)
  13. index 2:(data V2, parent -1)
  14. index 3:(data V3, parent -1)
  15. index 4:(data V4, parent -1)
  16. index 5:(data V5, parent -1)
  17. index 6:(data V6, parent -1)
  19. 以堆结构存放弧信息:
  20. 输入第1条弧信息(顶点1 顶点2 权值)：V3,V1,1
  21. 输入第2条弧信息(顶点1 顶点2 权值)：V3,V2,5
  22. 输入第3条弧信息(顶点1 顶点2 权值)：V3,V5,6
  23. 输入第4条弧信息(顶点1 顶点2 权值)：V3,V6,4
  24. 输入第5条弧信息(顶点1 顶点2 权值)：V3,V4,5
  25. 输入第6条弧信息(顶点1 顶点2 权值)：V1,V2,6
  26. 输入第7条弧信息(顶点1 顶点2 权值)：V2,V5,3
  27. 输入第8条弧信息(顶点1 顶点2 权值)：V5,V6,6
  28. 输入第9条弧信息(顶点1 顶点2 权值)：V6,V4,2
  29. 输入第10条弧信息(顶点1 顶点2 权值)：V4,V1,5
  30. 打印堆结构中的数据:
  31. index 1: arch:(3,1),weight 1)
  32. index 2: arch:(3,2),weight 5)
  33. index 3: arch:(3,5),weight 6)
  34. index 4: arch:(3,6),weight 4)
  35. index 5: arch:(3,4),weight 5)
  36. index 6: arch:(1,2),weight 6)
  37. index 7: arch:(2,5),weight 3)
  38. index 8: arch:(5,6),weight 6)
  39. index 9: arch:(6,4),weight 2)
  40. index 10: arch:(4,1),weight 5)
  41. 对存放了弧信息的堆进行排序,在排序过程中输入最小生成树的边
  42. 1)建立一个小顶堆!
  43. 打印堆结构中的数据:
  44. index 1: arch:(3,1),weight 1)
  45. index 2: arch:(6,4),weight 2)
  46. index 3: arch:(2,5),weight 3)
  47. index 4: arch:(3,6),weight 4)
  48. index 5: arch:(3,4),weight 5)
  49. index 6: arch:(1,2),weight 6)
  50. index 7: arch:(3,5),weight 6)
  51. index 8: arch:(5,6),weight 6)
  52. index 9: arch:(3,2),weight 5)
  53. index 10: arch:(4,1),weight 5)
  54. 2)依次输出堆顶元素并重新调整成小顶堆!
  55. 新堆顶的弧信息: (3,1) 1    是最小生成树的弧!
  56. 新堆顶的弧信息: (6,4) 2    是最小生成树的弧!
  57. 新堆顶的弧信息: (2,5) 3    是最小生成树的弧!
  58. 新堆顶的弧信息: (3,6) 4    是最小生成树的弧!
  59. 新堆顶的弧信息: (4,1) 5
  60. 新堆顶的弧信息: (3,4) 5
  61. 新堆顶的弧信息: (3,2) 5    是最小生成树的弧!
  62. 新堆顶的弧信息: (5,6) 6
  63. 新堆顶的弧信息: (3,5) 6
  65. Process finished with exit code 0

 

版权声明：本文为aimmiao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/aimmiao/p/10123964.html