图->连通性->最小生成树(克鲁斯卡尔算法)
文字描述
上一篇博客介绍了最小生成树(普里姆算法)，知道了普里姆算法求最小生成树的时间复杂度为n^2, 就是说复杂度与顶点数无关，而与弧的数量没有关系；
而用克鲁斯卡尔(Kruskal)算法求最小生成树则恰恰相反。它的时间复杂度为eloge (e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法求最小生成树的步骤为：假设连通网N={V,{E}}, 则令最小生成树的初始状态为只有n个顶点而无边的非连通图 T=(V, {}}, 图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量中，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
示意图：
算法分析：
实现克鲁斯卡尔的话，可以借助于之前介绍的”堆”(堆排序)和树的等价划分的方法。用”堆”来存放网中的边，则每次选择最小代价的边仅需loge的时间(第一次需e)。又生成树T的每个连通分量可看成一个等价类，则构造T加入新的边的过程类似于求等价类的过程，由此可用MFSet类型来描述顶点，用堆Heap存放弧结点信息，使构造T的过程仅需eloge的时间，由此，克鲁斯
代码实现
1 // 2 // Created by lady on 18-12-15. 3 // 4 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <string.h> 8 9 #define MAX_NODE_NUM 20 10 #define MAX_ARCH_NUM 30 11 12 #define EQ(a, b) ((a)==(b)) 13 #define LT(a, b) ((a) <(b)) 14 #define LQ(a, b) ((a)<=(b)) 15 16 17 typedef struct PTNode{ 18 char data[10]; 19 int index; 20 int parent; 21 }PTNode; 22 23 typedef struct{ 24 PTNode node[MAX_NODE_NUM+1]; 25 int n; 26 }MFSet; 27 28 typedef struct ArcBox{ 29 int vex1, vex2; 30 int weight; 31 }ArcBox; 32 33 typedef struct{ 34 ArcBox r[MAX_ARCH_NUM+1]; 35 int len; 36 }HeapType; 37 38 /* param1 S: S是已存在的集合 39 * param2 index: index是S中某个子集的成员的下标值 40 * result: 查找函数，确定S中位置为index所属子集Si，并返回其子集中的根结点的位置。 41 */ 42 static int findMFSet(MFSet *S, int index) 43 { 44 if(index < 1 || index > S->n) 45 return -1; 46 int j = 0; 47 for(j=index; S->node[j].parent>0; j=S->node[j].parent); 48 return j; 49 } 50 51 /* 52 * 集合S中位置为index_i和index_j所在的子集互不相交。 53 * result: 将置为index_i和index_j所在的互不相交的子集合并为一个子集。 54 */ 55 static int mergeMFSet(MFSet *S, int index_i, int index_j) 56 { 57 int loc_i = -1, loc_j = -1; 58 if((loc_i=findMFSet(S, index_i)) < 0){ 59 return -1; 60 } 61 if((loc_j=findMFSet(S, index_j)) < 0){ 62 return -1; 63 } 64 if(loc_i == loc_j){ 65 return -1; 66 } 67 //结点数少的子集指向结点数大的子集 68 if(S->node[loc_i].parent > S->node[loc_j].parent){ 69 S->node[loc_j].parent += S->node[loc_i].parent; 70 S->node[loc_i].parent = loc_j; 71 }else{ 72 S->node[loc_i].parent += S->node[loc_j].parent; 73 S->node[loc_j].parent = loc_i; 74 } 75 return 0; 76 } 77 78 static int initialMFSet(MFSet *S, int n) 79 { 80 int i = 0; 81 S->n = n; 82 for(i=1; i<=S->n; i++) 83 { 84 printf("输入第%d个子集:", i); 85 scanf("%s", S->node[i].data); 86 S->node[i].parent = -1; 87 S->node[i].index = i; 88 } 89 return 0; 90 } 91 92 /* 93 * 返回结点中数据等于data的下标值 94 */ 95 static int getLocaofVex(MFSet *S, char data[]) 96 { 97 int i = 0; 98 for(i=1; i<=S->n; i++){ 99 if(!strncasecmp(S->node[i].data, data, sizeof(S->node[0].data))){ 100 return S->node[i].index; 101 } 102 } 103 return -1; 104 } 105 106 static void printMFSet(MFSet *S) 107 { 108 printf("打印MFSet结构中的数据:\n"); 109 int i = 0; 110 for(i=1; i<=S->n; i++){ 111 printf("index %d:(data %s, parent %d)\n", S->node[i].index, S->node[i].data, S->node[i].parent); 112 } 113 printf("\n"); 114 } 115 116 117 118 ////////////////////////////////////////////// 119 120 static int printHeap(HeapType *H) 121 { 122 printf("打印堆结构中的数据:\n"); 123 int i = 0; 124 for(i=1; i<=H->len; i++){ 125 printf("index %d: arch:(%d,%d),weight %d)\n", i, H->r[i].vex1, H->r[i].vex2, H->r[i].weight); 126 } 127 return 0; 128 } 129 130 static int initialHeap(HeapType *H, MFSet *S, int n) 131 { 132 H->len = n; 133 int i = 0; 134 char s1[10] = {0}; 135 char s2[10] = {0}; 136 char s3[10] = {0}; 137 int weight = 0; 138 139 char tmp[30] = {0}; 140 for(i=1; i<=H->len; i++) 141 { 142 printf("输入第%d条弧信息(顶点1 顶点2 权值)：", i); 143 memset(tmp, 0, sizeof(tmp)); 144 scanf("%s", tmp); 145 sscanf(tmp, "%[^\',\'],%[^\',\'],%s[^\\n]", s1, s2, s3); 146 H->r[i].vex1 = getLocaofVex(S, s1); 147 H->r[i].vex2 = getLocaofVex(S, s2); 148 H->r[i].weight = atoi(s3); 149 } 150 return 0; 151 } 152 153 /* 154 *已知H->r[s,...,m]中记录的关键字除H->r[s].key之外均满足的定义 155 *本函数调整H-r[s]的关键字，使H->r[s,...,m]成为一个小顶堆(对其中 156 *记录的弧的权值而言) 157 */ 158 void HeapAdjust(HeapType *H, int s, int m) 159 { 160 ArcBox rc = H->r[s]; 161 int j = 0; 162 //沿weight较小的孩子结点向下筛选 163 for(j=2*s; j<=m; j*=2){ 164 //j为weight较小的孩子结点下标 165 if(j<m && (!LQ(H->r[j].weight, H->r[j+1].weight))) 166 j+=1; 167 if(LQ(rc.weight, H->r[j].weight)) 168 break; 169 H->r[s] = H->r[j]; 170 s=j; 171 } 172 H->r[s] = rc; 173 } 174 175 void HeapSort(HeapType *H, MFSet *S) 176 { 177 int i = 0; 178 printf("1)建立一个小顶堆!\n"); 179 //把H->r[1,...,H->length]建成小顶堆 180 for(i=H->len/2; i>=1; i--){ 181 HeapAdjust(H, i, H->len); 182 } 183 printHeap(H); 184 printf("2)依次输出堆顶元素并重新调整成小顶堆!\n"); 185 ArcBox tmp; 186 for(i=H->len; i>1; i--){ 187 tmp = H->r[1]; 188 H->r[1] = H->r[i]; 189 H->r[i] = tmp; 190 HeapAdjust(H, 1, i-1); 191 printf("新堆顶的弧信息: (%d,%d) %d", tmp.vex1, tmp.vex2, tmp.weight); 192 if(mergeMFSet(S, tmp.vex1, tmp.vex2) > -1){ 193 printf("\t是最小生成树的弧!\n"); 194 }else{ 195 printf("\n"); 196 } 197 } 198 } 199 200 201 202 203 int main(int argc, char *argv[]) 204 { 205 int nodes=0; 206 int archs=0; 207 printf("输入顶点数和弧数:"); 208 scanf("%d,%d", &nodes, &archs); 209 210 printf("\n以MFSet结构存放顶点信息:\n"); 211 MFSet S; 212 initialMFSet(&S, nodes); 213 printMFSet(&S); 214 215 printf("以堆结构存放弧信息:\n"); 216 HeapType H; 217 initialHeap(&H, &S, archs); 218 printHeap(&H); 219 220 printf("对存放了弧信息的堆进行排序,在排序过程中输入最小生成树的边\n"); 221 HeapSort(&H, &S); 222 return 0; 223 }
最小生成树(克鲁斯卡尔算法)
代码运行
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled 输入顶点数和弧数:6,10 以MFSet结构存放顶点信息: 输入第1个子集:V1 输入第2个子集:V2 输入第3个子集:V3 输入第4个子集:V4 输入第5个子集:V5 输入第6个子集:V6 打印MFSet结构中的数据: index 1:(data V1, parent -1) index 2:(data V2, parent -1) index 3:(data V3, parent -1) index 4:(data V4, parent -1) index 5:(data V5, parent -1) index 6:(data V6, parent -1) 以堆结构存放弧信息: 输入第1条弧信息(顶点1 顶点2 权值)：V3,V1,1 输入第2条弧信息(顶点1 顶点2 权值)：V3,V2,5 输入第3条弧信息(顶点1 顶点2 权值)：V3,V5,6 输入第4条弧信息(顶点1 顶点2 权值)：V3,V6,4 输入第5条弧信息(顶点1 顶点2 权值)：V3,V4,5 输入第6条弧信息(顶点1 顶点2 权值)：V1,V2,6 输入第7条弧信息(顶点1 顶点2 权值)：V2,V5,3 输入第8条弧信息(顶点1 顶点2 权值)：V5,V6,6 输入第9条弧信息(顶点1 顶点2 权值)：V6,V4,2 输入第10条弧信息(顶点1 顶点2 权值)：V4,V1,5 打印堆结构中的数据: index 1: arch:(3,1),weight 1) index 2: arch:(3,2),weight 5) index 3: arch:(3,5),weight 6) index 4: arch:(3,6),weight 4) index 5: arch:(3,4),weight 5) index 6: arch:(1,2),weight 6) index 7: arch:(2,5),weight 3) index 8: arch:(5,6),weight 6) index 9: arch:(6,4),weight 2) index 10: arch:(4,1),weight 5) 对存放了弧信息的堆进行排序,在排序过程中输入最小生成树的边 1)建立一个小顶堆! 打印堆结构中的数据: index 1: arch:(3,1),weight 1) index 2: arch:(6,4),weight 2) index 3: arch:(2,5),weight 3) index 4: arch:(3,6),weight 4) index 5: arch:(3,4),weight 5) index 6: arch:(1,2),weight 6) index 7: arch:(3,5),weight 6) index 8: arch:(5,6),weight 6) index 9: arch:(3,2),weight 5) index 10: arch:(4,1),weight 5) 2)依次输出堆顶元素并重新调整成小顶堆! 新堆顶的弧信息: (3,1) 1 是最小生成树的弧! 新堆顶的弧信息: (6,4) 2 是最小生成树的弧! 新堆顶的弧信息: (2,5) 3 是最小生成树的弧! 新堆顶的弧信息: (3,6) 4 是最小生成树的弧! 新堆顶的弧信息: (4,1) 5 新堆顶的弧信息: (3,4) 5 新堆顶的弧信息: (3,2) 5 是最小生成树的弧! 新堆顶的弧信息: (5,6) 6 新堆顶的弧信息: (3,5) 6 Process finished with exit code 0
版权声明：本文为aimmiao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。