Kruskal algoritması
Kenarları sırala, en kısasını al, asla döngü kapatma. Kruskal algoritması belki de var olan en basit açgözlü algoritmadır, yine de bir grafın tüm düğümlerini bağlamanın en ucuz yolunu her zaman bulur.
Fikir
Minimum kapsayan ağaç, ağırlıklı bir grafın tüm düğümlerini mümkün olan en küçük toplam kenar uzunluğuyla bağlar. Kruskal algoritması bir başlangıçtan tek bir ağaç büyütmez. Tüm grafa birden bakar, her düğümü kendi başına bir parça olarak alarak başlar ve tek bir parça kalana kadar parçaları mevcut en kısa kenarla birleştirmeye devam eder.
Adım adım
Kenarları en kısadan en uzuna sıralayın. Bu sırayla deneyin. Bir kenarın iki ucu farklı parçalardaysa onu ağaca ekleyin: iki parça bir olur. İki uç da zaten aynı parçadaysa kenar bir döngü kapatır, bu yüzden onu atlayın. n düğümle ağaç n − 1 kenardan sonra tamamlanır ve kalan kenarlara hiç bakmak gerekmez.
Bir örnek
Uzunluğu 1 olan A–B, 2 olan B–C, 3 olan A–C, 4 olan C–D ve 5 olan B–D kenarlarını alın. Kruskal önce A–B kenarını, sonra C düğümünü A–B parçasına bağlayan B–C kenarını ekler. Ardından A–C gelir, ama A ve C zaten aynı parçadadır; bu yüzden A–B–C döngüsünü kapatır ve atlanır. C–D kenarı D düğümünü bağlar ve artık dört düğümün hepsi üç kenarlı, toplam uzunluğu 7 olan tek bir ağaç oluşturur. En uzun kenar olan B–D hiç denenmez bile.
Union-find
Kruskal algoritmasının sorduğu tek zor soru şudur: bu iki düğüm zaten aynı parçada mı? Bunu bir union-find yapısı yanıtlar. Her parça, bir temsilciyi gösteren küçük bir bağlantılar ağacıdır. Find bağlantıları izleyerek temsilciye ulaşır; union bir temsilciyi diğerinin altına bağlar. Ziyaret edilen her düğümü doğrudan temsilciye yönlendiren yol sıkıştırma ve boyuta göre birleştirme, bağlantıları öyle kısa tutar ki her soru neredeyse sabit zaman alır.
Tarihçe ve hız
Joseph Kruskal algoritmayı 1956'da Proceedings of the American Mathematical Society'de kısa bir makaleyle yayımladı. En yavaş kısım kenarları sıralamaktır, bu yüzden E kenar için iş E log E ile büyür. Kenarlar zaten sıralıysa ya da uzunlukları küçük tam sayılarsa neredeyse doğrusaldır.
Keşfedin
Uygulamayı açın ve Adım'a basın. Denenecek kenarlar grafın altında, en kısadan başlayarak listelenir. İki parçayı birleştiren her kenar yeşile döner; döngü kapatacak her kenar kırmızı kesik çizgiyle çizilir. Grafın farklı yerlerinde birkaç küçük parçanın büyüyüp birleşmesini izleyin ve son kenarların çoğu zaman hiç denenmediğine dikkat edin.
Sık sorulan sorular
Kruskal algoritması kenarları neden sıralar?
Eklediği her kenar, hâlâ iki parçayı birleştiren en kısa kenar olsun diye. Bu açgözlü seçim kesme özelliği sayesinde her zaman güvenlidir; atlanan her kenar da kapatacağı döngüdeki en uzun kenardır, bu yüzden ona hiç gerek yoktur.
Ayrık küme yapısı nedir?
Union-find'ın başka bir adı: ayrı kümelerden oluşan bir koleksiyonu, burada büyüyen ormanın parçalarını, tutan ve bir öğenin hangi kümeye ait olduğunu söyleyip iki kümeyi hızla birleştirebilen bir yapı.
Kruskal algoritması bağlı olmayan bir grafta çalışır mı?
Evet. Grafın her bağlı parçası için bir ağaçla, yani bir minimum kapsayan ormanla biter, çünkü hiçbir kenar bağlı olmayan parçaları birleştiremez.
Kruskal algoritması başka bir şey için kullanılır mı?
Son parçalar birleşmeden önce erken durdurulursa düğümleri kümelere ayırır; buna tek bağlantılı kümeleme denir. Rastgele kenar uzunlukları olan bir ızgarada çalıştırılırsa bir labirent üretir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Kruskal algoritmasını deneyin