# Kruskal algorithm & & joint search set

now let's talk about another method for finding the minimum spanning tree - Kruskal algorithm. We know that there can be no loop in the minimum spanning tree, so we skip when we encounter the edge forming the loop, but how can we until the loop is formed? At this time, we need to judge whether the two vertices are connected. The methods to judge the connection include deep search and wide search, but their efficiency is relatively low. The more efficient method is joint search.
put all vertices into a joint query set to judge whether the two vertices are connected. Just judge whether the two vertices are in the same set (i.e. whether they have a common ancestor).
let's talk about and look up the set first. When reading a connected edge (U, V), first judge whether u and V are in the same set. If so, there is no need to merge; If not, a Union operation is used to merge the sets of u and V, so that any two elements in the two sets are connected.
A very important step in                    joint search

```void init() {//Indicates that each point is a tree with only one node
int i;
for (i = 1; i <= n; i++) {
f[i] = i;
}
return;
}
```

Then according to the given information, these trees are combined into a big tree

```int main(void) {
int i, x, y;
scanf("%d %d", &n, &m);
init();

for (i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);//Input connected edge
merge(x, y);
}

for (i = 1; i <= n; i++) {
if (f[i] == i)
sum++;
}
printf("%d\n", sum);//sum represents the number of different sets
return 0;
}
```
```void merge(int v, int u) {
int t1, t2;//The ancestors of V and u are represented by T1 and T2
t1 = getf(v);
t2 = getf(u);
if (t1 != t2) {//If they are no longer in the same set
f[t2] = t1;//Just merge them
}
return;
}
```
```//Find dad's recursive function
int getf(int v) {
if (f[v] == v)//The ancestor of an ancestor is himself
return v;
else {
//Path compression. Every time the function returns,
//By the way, change the ancestor of the person you meet on the road to the number of the ancestor you finally find
f[v] = getf(f[v]);
return f[v];
}
}
```

because you want to sort, set the edge and weight directly as a structure

```int main(void) {
int count = 0;//Used to count
int n, m;
int sum = 0;
scanf("%d %d", &n, &m);//n is the number of vertices and m is the number of edges
int i;
//Enter the relationship between edges
for (i = 1; i <= m; i++) {
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
}
//Sort from small to large according to the weight
quicksort(1, m);
//Parallel query set initialization
for (i = 1; i <= n; i++)
f[i] = i;
//Traverse all edges
for (i = 1; i <= m; i++) {
//Determine whether two vertices are in the same set
if (merge(e[i].u, e[i].v)) {//If the description is not in the same set, this edge can be selected
count++;
sum += e[i].w;
}
if (count == n - 1)
break;
}
printf("%d\n", sum);
return 0;
}
```

Next is the complete Kruskal algorithm

```#include<stdio.h>
int f[1000];
struct edge {
int u, v, w;//Two vertices, one weight
};
struct edge e[10];//Define structure array

void quicksort(int left, int right) {
struct edge t;
int i, j, mid;
i = left, j = right;
mid = e[(left + right) / 2].w;
do {
while (e[i].w < mid) i++;
while (e[j].w > mid) j--;
if (i <= j) {
t = e[i];
e[i] = e[j];
e[j] = t;
i++;
j--;
}

} while (i <= j);
if (i < right) quicksort(i, right);
if (left < j) quicksort(left, j);
}

//And look up the set to find the ancestor function
int getf(int v) {
if (f[v] == v)//Found an ancestor
return v;
else {
f[v] = getf(f[v]);
return f[v];
}
}

//Join two subset functions
int merge(int u, int v) {
int t1, t2;
t1 = getf(u);
t2 = getf(v);
if (t1 != t2) {//Judge whether two points are in the same set
f[t2] = t1;
return 1;
}
return 0;
}

int main(void) {
int count = 0;//Used to count
int n, m;
int sum = 0;
scanf("%d %d", &n, &m);//n is the number of vertices and m is the number of edges
int i;
//Enter the relationship between edges
for (i = 1; i <= m; i++) {
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
}
quicksort(1, m);
f[i] = i;

for (i = 1; i <= m; i++) {
//Determine whether two vertices are in the same set
if (merge(e[i].u, e[i].v)) {//If the description is not in the same set, this edge can be selected
count++;
sum += e[i].w;
}
if (count == n - 1)	//Parallel query set initialization
for (i = 1; i <= n; i++)

break;
}
printf("%d\n", sum);
return 0;
}
```

Keywords: Algorithm

Added by stockdalep on Fri, 11 Feb 2022 14:19:33 +0200