Minimum Spanning Tree adalah sebuah permasalahan untuk membentuk sebuah tree yang mengunjungi semua vertex yang ada dengan weight paling minimum.

Terdapat 2 implementasi yang terkenal untuk mengimplementasikan Minimum Spanning Tree, yaitu Algoritma Kruskal (O($E log V$)) dan Algoritma Prim (O($(V+E) log V$)). Namun yang akan kita bahas saat ini adalah Algoritma Kruskal.

Algoritma Kruskal menambahkan edge satu per satu sehingga menjadi Spanning Tree. Algoritma Kruskal merupakan pendekatan greedy di mana pada setiap iterasi mencari edge dengan weight terkecil untuk ditambahkan sehingga dapat membentuk Spanning Tree.

Pada Algoritma Kruskal, untuk mendapatkan Minimum Spanning Tree, berikut merupakan 4 langkah yang dilakukan:

1. Buat semua vertex menjadi tree individu (hanya berisi satu vertex)
2. Sort secara non-descending (tidak menurun) semua edge berdasarkan weight-nya
3. Ambil edge dengan weight terkecil. Apabila terbentuk cycle pada Spanning Tree, maka lewati edge tersebut. Apabila tidak, tambahkan edge tersebut pada Spanning Tree.
4. Lakukan langkah ke-3 hingga terbentuk V – 1 edge pada Spanning Tree.

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

Disjoint-Set Union merupakan sebuah struktur data yang menyimpan sekumpulan himpunan yang tidak saling tumpang tindih (non-overlapping sets). Pada Algoritma Kruskal, DSU digunakan untuk memeriksa apakah penambahan suatu edge membentuk cycle dan untuk menggabungkan 2 tree menjadi satu. Secara umum, fungsi yang ada dalam DSU adalah find dan union.

find adalah fungsi untuk memeriksa parent dari suatu vertex. Fungsi find digunakan untuk memeriksa apakah 2 vertex terdapat dalam satu tree yang sama atau tidak dengan memeriksa parent dari vertex tersebut. Jika memiliki parent yang sama, maka 2 vertex tersebut sudah berada pada satu tree. Untuk melakukan pencarian parent suatu vertex, kita dapat melakukannya secara iteratif maupun rekursif. Implementasi kali ini menggunakan rekursif.

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

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

union adalah fungsi untuk menggabungkan 2 tree menjadi satu dengan menjadikan parent dari sebuah tree sebagai child pada tree satunya.

void union_set(vector<long> &parent, long vertex1, long vertex2)
{
    int parent1 = find_parent(parent, vertex1);
    int parent2 = find_parent(parent, vertex2);

    if (parent1 != parent2)
        parent[parent2] = parent1;
}

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());
    /*
    Penulis sengaja meletakkan weight dari edge pada bagian awal pair,
    sehingga edge list akan disort berdasarkan weight dari edge
    */
    
    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;
        }
    }
}