- Şu anki
- Ağaçta
- Ağacın yanında
- Şimdiye kadarki en iyi kenar
- Döngü kapatırdı
Minimum kapsayan ağaç
Her kasabayı kabloyla, her evi su borusuyla ya da bir ağdaki her bilgisayarı olabildiğince az malzeme kullanarak bağlamak istiyorsunuz. Cevap minimum kapsayan ağaçtır: her düğümü en düşük toplam uzunlukla bağlayan kenar kümesi. Kruskal ya da Prim algoritmasını seçin ve ağacın her seferinde izin verilen en kısa kenarla büyüdüğünü adım adım izleyin. 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. Algoritmayı seçin: Kruskal kenarları en kısadan en uzuna dener, Prim başlangıçtan tek bir ağaç büyütür; bir düğümü Prim'in başlangıcı yapmak için ona tıklayın. Her kenardaki sayı o kenarın uzunluğudur. Grafın altında denenecek kenarların listesi ya da katılmayı bekleyen düğümler, ağaca giden en iyi kenarlarının uzunluğuyla birlikte yer alır. 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
- Kruskal ya da Prim algoritmasını seçin. Prim için bir düğümü başlangıç yapmak üzere ona tıklayın.
- 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.
- Kenarların ağaca katılmasını ve toplam uzunluğun artmasını izleyin. Yeni graf, denemeniz için başka bir graf oluşturur.
Kruskal algoritması
Tüm kenarları en kısadan en uzuna sıralayın ve bu sırayla deneyin. Bir kenar henüz bağlı olmayan iki parçayı birleştiriyorsa ağaca eklenir. İki ucu ağaç üzerinden zaten bağlıysa bir döngü kapatır, bu yüzden atlanır. Ağaçta düğüm sayısından bir eksik kenar olduğunda durun. İki düğümün zaten bağlı olup olmadığını hızla anlamak için Kruskal algoritması parçaları bir union-find yapısında tutar.
Prim algoritması
Tek düğümlü bir ağaçla başlayın. Ağacın dışındaki her düğüm, ağaca giden en kısa kenarını hatırlar. Kenarı en kısa olan düğümü o kenarla birlikte tekrar tekrar ekleyin ve onun kenarlarını inceleyin: bunlardan biri bir komşuya ağaca daha kısa bir yol verebilir. Prim algoritması Dijkstra algoritmasına benzer, ama başlangıçtan itibaren tüm uzaklıkları değil, tek tek kenarları karşılaştırır. İki algoritma da her zaman aynı toplam uzunlukla biter.
Sık sorulan sorular
Minimum kapsayan ağaç nedir?
Kenarlarının uzunlukları olan bağlantılı bir grafta kapsayan ağaç, tüm düğümleri hiç döngü olmadan bağlayan bir kenar kümesidir; n düğümde her zaman n − 1 kenarı vardır. Minimum kapsayan ağaç, toplam uzunluğu olabildiğince küçük olan kapsayan ağaçtır.
Kruskal ve Prim algoritmaları arasındaki fark nedir?
Kruskal algoritması tüm grafın kenarlarına en kısadan en uzuna doğru bakar ve ayrı parçaları tek bir ağaçta birleştirir. Prim algoritması bir başlangıçtan tek bir ağaç büyütür ve her zaman ağaçtan çıkan en kısa kenarı ekler. İkisi de açgözlüdür ve aynı toplam uzunlukta bir ağaç bulur; Kruskal seyrek graflara, Prim yoğun graflara uygundur.
Minimum kapsayan ağaç tek midir?
Tüm kenar uzunlukları farklıysa evet. Bazı uzunluklar eşitse aynı en küçük toplama sahip birkaç ağaç olabilir ve algoritmalar, eşit kenarlar arasında nasıl seçim yaptıklarına göre farklı ağaçlar seçebilir.
Minimum kapsayan ağaç en kısa yollarla aynı şey midir?
Hayır. Minimum kapsayan ağaç tüm kenarların toplam uzunluğunu küçük tutar, ama ağaçta iki düğüm arasındaki yol, onların en kısa yolundan çok daha uzun olabilir. En kısa yollar için Dijkstra algoritmasını kullanın.
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