Pengantar

Selamat datang kembali di seri Algoritma Graf! Pohon Merentang Minimum (MST) menghubungkan setiap simpul dalam graf berbobot dengan total bobot sisi sekecil mungkin, tanpa siklus.

Algoritma Kruskal membangun MST secara rakus: algoritma ini mengurutkan sisi dari yang termurah hingga termahal, lalu menambahkan setiap sisi selama penambahan itu tidak membentuk siklus. Cara cepat untuk mendeteksi siklus adalah menggunakan struktur data yang disebut union-find (juga dikenal sebagai disjoint-set).

Graf ini tidak berarah dan berbobot, diberikan sebagai n (simpul 0 hingga n - 1) dan edges, sebuah array datar berisi tripel [u0, v0, w0, ...] untuk sisi tidak berarah u - v dengan bobot w.

Mari kita mulai!