Ağaç kenarları
Toplam uzunluk
İncelenen kenar

  • Şu anki
  • Ağaçta
  • Ağacın yanında
  • Şimdiye kadarki en iyi kenar

Prim algoritması hakkında daha fazla

Prim algoritması

Prim algoritması, tüm düğümleri bağlayan en ucuz kenar kümesi olan minimum kapsayan ağacı, bir başlangıçtan tek bir ağaç büyüterek kurar. Her adımda, ağaçtan en kısa kenarla ulaşılabilen düğümü ekler. Oradan başlamak için bir düğüme tıklayın ve bekleyen düğümleri, onların en iyi kenarlarını ve büyüyen ağacı görmek için adım adım ilerleyin. Ağacın büyümesini izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Bir düğümü başlangıç yapmak için ona tıklayın: ağaç oradan büyür. Her kenardaki sayı o kenarın uzunluğudur. Grafın altında katılmayı bekleyen düğümler, ağaca giden en iyi kenarlarının uzunluğuyla birlikte yer alır; bu kenar kesik çizgiyle çizilir. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Bir düğümü başlangıç yapmak için ona tıklayın: ağaç oradan büyür.
  2. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  3. Grafın altındaki bekleyen düğümleri, her birinin ağaca giden en iyi kenarıyla birlikte izleyin. Yeni graf, denemeniz için başka bir graf oluşturur.

Prim algoritması nasıl çalışır

Tek düğümlü bir ağaçla başlayın. Ağacın dışındaki her düğüm, varsa ağaca giden en kısa kenarını hatırlar. Kenarı en kısa olan düğümü tekrar tekrar alın, onu bu kenarla ağaca ekleyin ve kenarlarına bakın: bir kenar bir komşunun şimdiye kadarki en iyi kenarından kısaysa, o komşunun yeni en iyi kenarı olur. Tüm düğümler katıldığında ağaçta düğüm sayısından bir eksik kenar vardır ve toplam uzunluğu mümkün olan en küçük değerdir.

Prim ve Dijkstra

Prim algoritması ile Dijkstra algoritması neredeyse aynı görünür: ikisi de bir başlangıçtan bir bölge büyütür ve bekleyen düğümleri bir öncelik kuyruğunda tutar. Fark, kuyruktaki sayıdadır. Dijkstra her düğümün başlangıçtan tüm uzaklığını tutar; Prim yalnızca ağaca giden tek en iyi kenarının uzunluğunu. Bu yüzden Dijkstra bir en kısa yollar ağacı, Prim ise toplam uzunluğu en küçük olan bir ağaç kurar ve bu iki ağaç çoğu zaman farklıdır.

Sık sorulan sorular

Prim algoritması nedir?

Ağırlıklı bir grafın minimum kapsayan ağacını, bir başlangıç düğümünden tek bir ağaç büyüterek ve her zaman ağacı dışındaki bir düğüme bağlayan en kısa kenarı ekleyerek kuran açgözlü bir algoritma.

Başlangıç düğümü önemli mi?

Yalnızca sıra için: Prim algoritması hangi başlangıçtan çalışırsa çalışsın aynı en küçük toplam uzunlukta bir kapsayan ağaçla biter. Bazı kenarların uzunlukları eşitse ağacın kendisi farklı olabilir.

Prim algoritmasını kim buldu?

İlk olarak 1930'da Vojtěch Jarník tanımladı. Robert Prim 1957'de, Edsger Dijkstra da 1959'da onu yeniden keşfetti; bu yüzden Jarník algoritması ya da Prim–Jarník algoritması olarak da bilinir.

Prim algoritması ne kadar hızlıdır?

İkili yığınla, V düğüm ve E kenar için iş E log V ile büyür. Yığın yerine basit bir diziyle yaklaşık V² adım sürer; bu da neredeyse her düğüm çiftinin bağlı olduğu yoğun graflar için daha iyidir.

Grafım bir yere gönderiliyor mu?

Hayır. Graf tarayıcınızda oluşturulur ve ağaç orada kurulur, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git