实现思路

  1. 将图中的边按从小到大的顺序排列
  2. 遍历边所在的数组
    • 如果边的两个顶点不存在于同一集合，则将两点所在的集合合并，两点连通
    • 否则跳过

模拟过程

image-20240331212158034

按边从小到大排序，构建辅助数组

算法实现

克鲁斯卡尔算法需要一个辅助数组，数据元素结构如下

1
2
3
4
5
typedef struct Edge{
    int head;
    int tail;
    int weight;
}Edge;

Edges数组需要根据边的长度weight从小到大进行排序,排序的算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*快速排序*/
void Sort(struct Edge edges[],int l,int r){
    if (l >= r) return;
    int i=l-1;
    int j=r+1;
    int mid=edges[(l+r)/2].weight;
    while(i<j){
        while(edges[++i].weight<mid);
        while(edges[--j].weight>mid);
        if(i<j){
            struct Edge tmp=edges[i];
            edges[i]=edges[j];
            edges[j]=tmp;
        }
    }
    Sort(edges,l,j);
    Sort(edges,j+1,r);
}

并查集相关操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*查找元素所在集合*/
int Find(int sets[],int x){
    int root=x;
    /*找到根节点*/
    while(sets[root]>=0)
        root=sets[root];
    int tmp=x;
    while(sets[tmp]>=0){
        int t=sets[tmp];/*保存父节点*/
        sets[tmp]=root; /*挂载到根节点*/
        tmp=t;/*成为父节点*/
    }
    return tmp;
}

/*判断两顶点是否在同一集合*/
int is_connected(int *sets,int head,int tail){
    int set1=Find(sets,head);
    int set2=Find(sets,tail);
    if(set1!=set2)
        return 0;
    else
        return 1;
}
/*将两个根节点所在的集合合并集合*/
void UnionSets(int sets[],int root1,int root2){
    if(root1==root2)    return;
    if(sets[root1]>=sets[root2]){
        sets[root1]+=sets[root2];/*累加树的结点*/
        sets[root2]=root1;/*小树挂载到大树*/
    }
    else{
        sets[root2]+=sets[root1];
        sets[root1]=root2;
    }
}
/*合并两个集合*/
void Union(int sets[],int node1,int node2){
    int root1=Find(sets,node1);
    int root2=Find(sets,node2);
    UnionSets(sets,root1,root2);
}

核心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*最小生成树算法*/
void Kruskal(int graph[6][6],int vtxnum){
    int sets[vtxnum];/*最小生成树的集合*/
    struct Edge edges[MAXSIZE];
    int size=0;
    
    /*根据边信息构建辅助数组*/
    for(int i=0;i<vtxnum;i++){
        for(int j=i;j<vtxnum;j++){/*遍历对角一半的邻接矩阵*/
            if(graph[i][j]!=0&&graph[i][j]!=INF){
                edges[size].weight=graph[i][j];
                edges[size].head=i;
                edges[size].tail=j;
                size++;
            }
        } 
    }
    /*初始化集合*/
    for(int i=0;i<size;i++){
        sets[i]=-1;
    }
    Sort(edges,0,size-1);
    for(int i=0;i<size;i++){
         printf("(%d,%d) weight:%d\n",edges[i].head,edges[i].tail,edges[i].weight);
    }
    for(int i=0;i<size;i++){
        //检查边是否在同一集合
        if(!is_connected(sets,edges[i].head,edges[i].tail)){
            printf("(%d,%d)权值为%d\n",edges[i].head
                                    ,edges[i].tail
                                    ,edges[i].weight);
            Union(sets,edges[i].head,edges[i].tail);
        }
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<stdio.h>
#define INF 1024
#define MAXSIZE 100
typedef struct Edge{
    int head;
    int tail;
    int weight;
}Edge;


/*快速排序*/
void Sort(struct Edge edges[],int l,int r){
    if (l >= r) return;
    int i=l-1;
    int j=r+1;
    int mid=edges[(l+r)/2].weight;
    while(i<j){
        while(edges[++i].weight<mid);
        while(edges[--j].weight>mid);
        if(i<j){
            struct Edge tmp=edges[i];
            edges[i]=edges[j];
            edges[j]=tmp;
        }
    }
    Sort(edges,l,j);
    Sort(edges,j+1,r);
}
/*查找元素所在集合*/
int Find(int sets[],int x){
    int root=x;
    /*找到根节点*/
    while(sets[root]>=0)
        root=sets[root];
    int tmp=x;
    while(sets[tmp]>=0){
        int t=sets[tmp];/*保存父节点*/
        sets[tmp]=root; /*挂载到根节点*/
        tmp=t;/*成为父节点*/
    }
    return tmp;
}

/*判断两顶点是否在同一集合*/
int is_connected(int *sets,int head,int tail){
    int set1=Find(sets,head);
    int set2=Find(sets,tail);
    if(set1!=set2)
        return 0;
    else
        return 1;
}
/*将两个根节点所在的集合合并集合*/
void UnionSets(int sets[],int root1,int root2){
    if(root1==root2)    return;
    if(sets[root1]>=sets[root2]){
        sets[root1]+=sets[root2];/*累加树的结点*/
        sets[root2]=root1;/*小树挂载到大树*/
    }
    else{
        sets[root2]+=sets[root1];
        sets[root1]=root2;
    }
}
/*合并两个集合*/
void Union(int sets[],int node1,int node2){
    int root1=Find(sets,node1);
    int root2=Find(sets,node2);
    UnionSets(sets,root1,root2);
}

/*最小生成树算法*/
void Kruskal(int graph[6][6],int vtxnum){
    int sets[vtxnum];/*最小生成树的集合*/
    struct Edge edges[MAXSIZE];
    int size=0;
    
    /*根据边信息构建辅助数组*/
    for(int i=0;i<vtxnum;i++){
        for(int j=i;j<vtxnum;j++){/*遍历对角一半的邻接矩阵*/
            if(graph[i][j]!=0&&graph[i][j]!=INF){
                edges[size].weight=graph[i][j];
                edges[size].head=i;
                edges[size].tail=j;
                size++;
            }
        } 
    }
    /*初始化集合*/
    for(int i=0;i<size;i++){
        sets[i]=-1;
    }
    Sort(edges,0,size-1);
    for(int i=0;i<size;i++){
         printf("(%d,%d) weight:%d\n",edges[i].head,edges[i].tail,edges[i].weight);
    }
    for(int i=0;i<size;i++){
        //检查边是否在同一集合
        if(!is_connected(sets,edges[i].head,edges[i].tail)){
            printf("(%d,%d)权值为%d\n",edges[i].head
                                    ,edges[i].tail
                                    ,edges[i].weight);
            Union(sets,edges[i].head,edges[i].tail);
        }
    }
}

int main(){
    /*
        v0 v1 v2 v3 v4 v5
    v0   0 6  5  1  INF INF
    v1  6  0  0  5  3  0
    v2  5 INF 0  4  INF  2
    v3  1  5  4  0  6  4
    v4 INF 3 INF 6  0   6 
    v5 INF INF 2 4  6  0
    */
    int graph[6][6]={{0,6,5,1,INF,INF},
                    {6,0,0,5,3,0},
                    {5,INF,0,4,INF,2},
                    {1,5,4,0,6,4},
                    {INF,3,INF,6,0,6},
                    {INF,INF,2,4,6,0}};
    Kruskal(graph,6);


    return 0;
}