Sisi pohon
Total panjang
Sisi diperiksa

  • Saat ini
  • Di dalam pohon
  • Di sebelah pohon
  • Sisi terbaik sejauh ini

Selengkapnya tentang algoritma Prim

Algoritma Prim

Algoritma Prim membangun pohon merentang minimum, yaitu himpunan sisi termurah yang menghubungkan setiap simpul, dengan menumbuhkan satu pohon dari awal. Di setiap langkah, algoritma ini menambahkan simpul yang bisa dicapai lewat sisi terpendek dari pohon. Klik simpul untuk mulai dari sana dan jalankan langkah demi langkah untuk melihat simpul yang menunggu, sisi terbaiknya, dan pohon yang tumbuh. 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. Klik simpul untuk menjadikannya awal: pohon tumbuh dari sana. Angka di tiap sisi adalah panjangnya. Di bawah graf ada simpul yang menunggu bergabung, masing-masing dengan panjang sisi terbaiknya ke pohon, yang digambar putus-putus. 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. Klik simpul untuk menjadikannya awal: pohon tumbuh dari sana.
  2. Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
  3. Perhatikan simpul yang menunggu di bawah graf, masing-masing dengan sisi terbaiknya ke pohon. Graf baru membuat graf lain untuk dicoba.

Cara kerja algoritma Prim

Mulailah dengan pohon berisi satu simpul. Setiap simpul di luar pohon mengingat sisi terpendeknya ke pohon, jika ada. Berulang kali ambil simpul dengan sisi terpendek, tambahkan simpul itu dan sisinya ke pohon, lalu periksa sisi-sisinya: jika ada yang lebih pendek dari sisi terbaik tetangga sejauh ini, sisi itu menjadi sisi terbaik tetangga tersebut. Saat semua simpul sudah bergabung, pohon punya satu sisi lebih sedikit dari jumlah simpul, dan total panjangnya sekecil mungkin.

Prim dan Dijkstra

Algoritma Prim dan algoritma Dijkstra tampak hampir sama: keduanya menumbuhkan wilayah dari awal dan menyimpan simpul yang menunggu dalam antrean prioritas. Bedanya ada pada angka di antrean. Dijkstra menyimpan seluruh jarak tiap simpul dari awal; Prim hanya menyimpan panjang satu sisi terbaiknya ke pohon. Jadi Dijkstra membangun pohon jalur terpendek, dan Prim pohon dengan total panjang terkecil, dan kedua pohon itu sering berbeda.

Pertanyaan yang sering diajukan

Apa itu algoritma Prim?

Algoritma greedy yang membangun pohon merentang minimum dari graf berbobot dengan menumbuhkan satu pohon dari simpul awal, selalu menambahkan sisi terpendek yang menghubungkan pohon dengan simpul di luarnya.

Apakah simpul awal berpengaruh?

Hanya pada urutannya: dari awal mana pun, algoritma Prim berakhir dengan pohon merentang yang total panjangnya sama-sama terkecil. Jika beberapa sisi sama panjang, pohonnya sendiri bisa berbeda.

Siapa yang menemukan algoritma Prim?

Vojtěch Jarník pertama kali menjelaskannya pada 1930. Robert Prim menemukannya kembali pada 1957 dan Edsger Dijkstra pada 1959, jadi algoritma ini juga disebut algoritma Jarník atau algoritma Prim–Jarník.

Seberapa cepat algoritma Prim?

Dengan binary heap, kerjanya tumbuh sebanding E log V untuk V simpul dan E sisi. Dengan array sederhana sebagai ganti heap, perlu sekitar V² langkah, yang lebih baik untuk graf padat yang hampir setiap pasang simpulnya terhubung.

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