Sisi pohon
Total panjang
Sisi diperiksa

  • Saat ini
  • Di dalam pohon
  • Akan membentuk siklus

Selengkapnya tentang algoritma Kruskal

Algoritma Kruskal

Algoritma Kruskal membangun pohon merentang minimum, yaitu himpunan sisi termurah yang menghubungkan setiap simpul, dengan cara paling sederhana yang bisa dibayangkan: ambil sisi dari terpendek ke terpanjang, dan simpan masing-masing kecuali jika akan membentuk siklus. Jalankan langkah demi langkah untuk melihat bagian-bagian terpisah tumbuh dan bergabung menjadi satu pohon, serta sisi yang dilewati. Tekan Putar untuk melihat pohon tumbuh, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Angka di tiap sisi adalah panjangnya. Di bawah graf ada sisi yang masih akan dicoba, dari terpendek ke terpanjang; sisi yang kedua ujungnya sudah terhubung akan membentuk siklus dan digambar putus-putus merah. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah.
  2. Geser penggeser langkah untuk melompat ke mana saja. Sisi yang masih akan dicoba didaftar di bawah graf, yang terpendek lebih dulu.
  3. Perhatikan sisi yang digambar putus-putus merah: sisi itu akan membentuk siklus. Graf baru membuat graf lain untuk dicoba.

Cara kerja algoritma Kruskal

Urutkan semua sisi dari terpendek ke terpanjang. Mulailah dengan setiap simpul sebagai bagian tersendiri. Coba sisi-sisi secara berurutan: jika sebuah sisi menghubungkan dua bagian berbeda, sisi itu masuk ke pohon dan kedua bagian menjadi satu; jika kedua ujungnya sudah berada di bagian yang sama, sisi itu akan membentuk siklus, jadi lewati. Berhenti saat semuanya menjadi satu bagian, yang terjadi setelah satu sisi lebih sedikit dari jumlah simpul, sering jauh sebelum sisi terakhir dicoba.

Union-find

Untuk setiap sisi, algoritma Kruskal harus bertanya apakah kedua ujungnya sudah terhubung. Struktur union-find menjawabnya dengan cepat: setiap bagian punya satu simpul wakil, find mengikuti tautan ke wakil itu, dan union menautkan satu wakil ke wakil lainnya. Dengan dua trik sederhana, kompresi jalur dan penggabungan menurut ukuran, setiap pertanyaan hampir memakan waktu konstan, jadi mengurutkan sisi adalah bagian paling lambat, dengan kerja yang tumbuh sebanding E log E.

Pertanyaan yang sering diajukan

Apa itu algoritma Kruskal?

Algoritma greedy yang membangun pohon merentang minimum dengan mengurutkan semua sisi dari terpendek ke terpanjang dan menambahkan setiap sisi yang tidak membentuk siklus dengan sisi yang sudah dipilih.

Bagaimana algoritma Kruskal mendeteksi siklus?

Sebuah sisi membentuk siklus tepat ketika kedua ujungnya sudah terhubung oleh sisi yang dipilih. Struktur union-find mencatat simpul mana yang terhubung dan menjawab pertanyaan itu hampir seketika.

Mengapa algoritma Kruskal berhasil?

Karena sifat siklus: sisi terpanjang pada siklus mana pun tidak pernah diperlukan untuk pohon merentang minimum. Setiap sisi yang dilewati Kruskal adalah yang terpanjang pada siklus yang akan dibentuknya, karena semua sisi sebelumnya lebih pendek atau sama panjang.

Kapan sebaiknya memakai Kruskal, bukan Prim?

Algoritma Kruskal sederhana dan cepat pada graf jarang, dan bekerja langsung pada daftar sisi biasa. Algoritma Prim cocok untuk graf padat dan graf yang disimpan sebagai daftar ketetanggaan. Keduanya menemukan pohon dengan total panjang yang sama.

Apakah graf saya dikirim ke mana pun?

Tidak. Graf dibuat dan pohon dibangun di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor