Minimum Spanning TreeLesson 40Preview gratis
DSA Kruskal's
Lesson ini bagian dari DSA · Semua level
Ringkasan
Kruskal mengurutkan seluruh sisi berdasarkan bobot, lalu memasukkan sisi satu per satu asalkan tidak membentuk siklus. Struktur data disjoint set (union-find) dipakai untuk memeriksa apakah dua simpul sudah berada dalam komponen yang sama. Algoritma ini bekerja dengan baik pada graf jarang dengan kompleksitas O(E log E).
Poin kunci
- Mengurutkan sisi dari bobot terkecil, lalu menyambung yang valid
- Union-find mendeteksi sisi yang akan membentuk siklus
- Berhenti setelah V-1 sisi terpilih
- Kompleksitas O(E log E), cocok untuk graf jarang
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.