Algoritma Kruskal
Urutkan sisi, ambil yang terpendek, jangan pernah membentuk lingkaran. Algoritma Kruskal mungkin algoritma greedy paling sederhana yang ada, tetapi selalu menemukan cara termurah untuk menghubungkan setiap simpul graf.
Idenya
Pohon merentang minimum menghubungkan setiap simpul graf berbobot dengan total panjang sisi sekecil mungkin. Algoritma Kruskal tidak menumbuhkan satu pohon dari awal. Algoritma ini melihat seluruh graf sekaligus, mulai dengan setiap simpul sebagai bagian tersendiri, dan terus menggabungkan bagian dengan sisi terpendek yang tersedia sampai hanya tersisa satu bagian.
Langkah demi langkah
Urutkan sisi dari terpendek ke terpanjang. Coba sisi-sisi dalam urutan itu. Jika kedua ujung sebuah sisi berada di bagian berbeda, tambahkan ke pohon: kedua bagian menjadi satu. Jika kedua ujungnya sudah di bagian yang sama, sisi itu akan membentuk siklus, jadi lewati. Dengan n simpul, pohon lengkap setelah n − 1 sisi, dan sisi yang tersisa tidak perlu dilihat lagi.
Contoh
Ambil sisi A–B dengan panjang 1, B–C 2, A–C 3, C–D 4, dan B–D 5. Kruskal menambahkan A–B, lalu B–C, yang menghubungkan C ke bagian A–B. Berikutnya A–C, tetapi A dan C sudah dalam satu bagian, jadi sisi itu akan membentuk siklus A–B–C dan dilewati. C–D menggabungkan D, dan kini keempat simpul membentuk satu pohon dengan tiga sisi, dengan total panjang 7. B–D, sisi terpanjang, bahkan tidak pernah dicoba.
Union-find
Satu-satunya pertanyaan sulit yang diajukan algoritma Kruskal adalah: apakah kedua simpul ini sudah di bagian yang sama? Struktur union-find menjawabnya. Setiap bagian adalah pohon kecil berisi tautan yang menunjuk ke wakil. Find mengikuti tautan ke wakil; union menautkan satu wakil di bawah wakil lainnya. Kompresi jalur, yang membuat setiap simpul yang dikunjungi langsung menunjuk ke wakil, dan penggabungan menurut ukuran menjaga tautan begitu pendek sehingga setiap pertanyaan hampir memakan waktu konstan.
Sejarah dan kecepatan
Joseph Kruskal menerbitkan algoritma ini pada 1956, dalam makalah pendek di Proceedings of the American Mathematical Society. Mengurutkan sisi adalah bagian paling lambat, jadi kerjanya tumbuh sebanding E log E untuk E sisi. Jika sisi sudah terurut, atau panjangnya bilangan bulat kecil, kerjanya hampir linear.
Jelajahi
Buka aplikasinya dan tekan Langkah. Sisi yang masih akan dicoba didaftar di bawah graf, yang terpendek lebih dulu. Setiap sisi yang menggabungkan dua bagian menjadi hijau; setiap sisi yang akan membentuk siklus digambar putus-putus merah. Lihat beberapa bagian kecil tumbuh di berbagai tempat graf lalu bergabung, dan perhatikan bahwa sisi-sisi terakhir sering tidak pernah dicoba.
Pertanyaan yang sering diajukan
Mengapa algoritma Kruskal mengurutkan sisi?
Agar setiap sisi yang ditambahkannya adalah sisi terpendek yang masih menghubungkan dua bagian. Pilihan greedy itu selalu aman karena sifat potong, dan setiap sisi yang dilewati adalah yang terpanjang pada siklus yang akan dibentuknya, jadi tidak pernah diperlukan.
Apa itu struktur himpunan saling lepas?
Nama lain union-find: struktur yang menyimpan kumpulan himpunan terpisah, di sini bagian-bagian hutan yang sedang tumbuh, dan bisa memberi tahu himpunan mana yang memuat suatu elemen serta menggabungkan dua himpunan dengan cepat.
Apakah algoritma Kruskal bisa dipakai pada graf tidak terhubung?
Ya. Algoritma ini berakhir dengan satu pohon untuk setiap bagian graf yang terhubung, yaitu hutan merentang minimum, karena tidak ada sisi yang bisa menggabungkan bagian yang tidak terhubung.
Apakah algoritma Kruskal dipakai untuk hal lain?
Menghentikannya lebih awal, sebelum bagian-bagian terakhir bergabung, mengelompokkan simpul menjadi klaster, yaitu pengklasteran single-linkage. Menjalankannya pada kisi dengan panjang sisi acak menghasilkan labirin.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba algoritma Kruskal