Ağaç kenarları
Toplam uzunluk
İncelenen kenar

  • Şu anki
  • Ağaçta
  • Döngü kapatırdı

Kruskal algoritması hakkında daha fazla

Kruskal algoritması

Kruskal algoritması, tüm düğümleri bağlayan en ucuz kenar kümesi olan minimum kapsayan ağacı akla gelebilecek en basit yolla kurar: kenarları en kısadan en uzuna alın ve döngü kapatmadığı sürece her birini tutun. Ayrı parçaların büyüyüp tek bir ağaçta birleşmesini ve atlanan kenarları 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. Her kenardaki sayı o kenarın uzunluğudur. Grafın altında denenecek kenarlar en kısadan en uzuna doğru yer alır; uçları zaten bağlı olan bir kenar bir döngü kapatır ve kırmızı 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. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın.
  2. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Denenecek kenarlar grafın altında, en kısadan başlayarak listelenir.
  3. Kırmızı kesik çizgiyle çizilen kenarlara dikkat edin: bunlar bir döngü kapatırdı. Yeni graf, denemeniz için başka bir graf oluşturur.

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

Tüm kenarları en kısadan en uzuna sıralayın. Her düğümü kendi başına bir parça olarak alarak başlayın. Kenarları sırayla deneyin: bir kenar iki farklı parçayı birleştiriyorsa ağaca girer ve iki parça bir olur; iki ucu zaten aynı parçadaysa bir döngü kapatır, bu yüzden onu atlayın. Her şey tek parça olduğunda durun. Bu, düğüm sayısından bir eksik kenardan sonra olur, çoğu zaman son kenar denenmeden çok önce.

Union-find

Kruskal algoritması her kenar için iki ucunun zaten bağlı olup olmadığını sormak zorundadır. Bir union-find yapısı bunu hızla yanıtlar: her parçanın bir temsilci düğümü vardır, find bağlantıları izleyerek ona ulaşır, union da bir temsilciyi diğerine bağlar. Yol sıkıştırma ve boyuta göre birleştirme adlı iki basit hileyle her soru neredeyse sabit zaman alır; bu yüzden en yavaş kısım kenarları sıralamaktır ve iş E log E ile büyür.

Sık sorulan sorular

Kruskal algoritması nedir?

Tüm kenarları en kısadan en uzuna sıralayıp zaten seçilmiş kenarlarla döngü kapatmayan her kenarı ekleyerek minimum kapsayan ağacı kuran açgözlü bir algoritma.

Kruskal algoritması döngüyü nasıl fark eder?

Bir kenar, tam olarak iki ucu seçilmiş kenarlarla zaten bağlıysa bir döngü kapatır. Bir union-find yapısı hangi düğümlerin bağlı olduğunu takip eder ve bu soruyu neredeyse anında yanıtlar.

Kruskal algoritması neden çalışır?

Döngü özelliği sayesinde: herhangi bir döngüdeki en uzun kenara minimum kapsayan ağaç için hiçbir zaman gerek yoktur. Kruskal'ın atladığı her kenar, kapatacağı döngüdeki en uzun kenardır, çünkü ondan önceki tüm kenarlar daha kısa ya da eşitti.

Prim yerine ne zaman Kruskal kullanmalıyım?

Kruskal algoritması basittir, seyrek graflarda hızlıdır ve doğrudan düz bir kenar listesi üzerinde çalışır. Prim algoritması yoğun graflara ve komşuluk listeleri olarak saklanan graflara uygundur. İkisi de aynı toplam uzunlukta bir ağaç bulur.

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