图->连通性->最小生成树(克鲁斯卡尔算法)

时间:2021-08-11 11:39:12

文字描述

  上一篇博客介绍了最小生成树(普里姆算法),知道了普里姆算法求最小生成树的时间复杂度为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