Minimum Spanning Tree is a problem to construct a tree that connects all vertex with minimum weight.

There are 2 implementations that are known to construct Minimum Spanning Tree: Kruskal Algorithm (O($E log V$)) and Prim ALgorithm (O($(V+E) log V$)). This module will explain Kruskal Algorithm only.

Kruskal Algorithm adds edge one by one until Spanning Tree is constructed. Kruskal Algorithm using greedy approach where each iteration adds edge with minimum weight to the tree.

This is the steps of Kruskal Algorithm:

1. Create all vertex to be an individual tree (has only a vertex)
2. Sort all edge descendingly based on their weight
3. pick an edge with smallest weight. If a cycle is formed in the Spanning Tree, skip that edge. If not, add that edge in the Spanning Tree.
4. Do the third step until all vertex is connected to the tree.

Source: https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/minimum-spanning-trees-kruskals-algorithm/

Disjoint-Set Union is a data structure that stores a collection of disjoint (non-overlapping) sets. On Kruskal ALgorithm, DSU is used to check if addition of an edge creates cycle or not and to combine 2 tree into one. Generally, function inside a DSU is find and union.

find is a function to check parent of a vertex. find is used to check if 2 vertex are members of the same tree. If both vertex eventually points to the same parent, those vertexes are members of the same tree. This is a recursive implementation of find.

long find_parent(vector<long> &parent, long v){
    if(v == parent[v]) return v;

    return find_parent(parent, parent[v]);
}  

union is a function to unite 2 tree into one by change the parent of a tree as a child in the other tree.

void union_set(vector<long> &parent, long vertex1, long vertex2){
    parent[vertex2] = parent[vertex1];
}

void kruskal(vector<pair<long, pair<long, long>>> &result){
    vector<long> parent;
    for(int i=0; i<vertexCount; i++) parent.push_back(i);

    sort(edgeList.begin(), edgeList.end());
    /*
    The weight of edges is placed as the first element so edge list
    would be sorted based on edge's waight first.
    */
    
    for(auto edge:edgeList){
        long vertex1 = edge.second.first;
        long vertex2 = edge.second.second;
        if(find_parent(parent, vertex1) != find_parent(parent, vertex2)){
            result.push_back(edge);
            union_set(parent, vertex1, vertex2);
            if(result.size() == vertexCount-1) return;
        }
    }
}