Motivasi

Kruskal menyimpan hutan sisi terpilih yang terus bertambah dalam struktur union-find. Untuk menambahkan sisi dengan aman, algoritma ini memeriksa apakah kedua titik ujung sudah berada dalam himpunan yang sama (hal itu akan membentuk siklus).

Mengapa mempelajari Kruskal?

• MST nyata: desain jaringan, pengelompokan, serta pemasangan kabel atau pembangunan jalan dengan biaya minimum.
• Union-find: struktur yang elegan dan dapat digunakan kembali untuk melacak keterhubungan, yang banyak muncul dalam ilmu komputer.
• Kebenaran algoritma greedy: contoh lain bahwa selalu memilih opsi aman yang paling murah menghasilkan optimum global.

Semua pohon merentang minimum dari suatu graf menggunakan multiset bobot sisi yang sama, jadi bobot total (dan sisi terbesar) bersifat unik.