Kruskal'ın algoritması - Kruskal's algorithm

Kruskal'ın algoritması , yönlenmemiş kenar ağırlıklı bir grafiğin minimum genişleyen ormanını bulur . Grafik bağlıysa , minimum bir kapsayan ağaç bulur . (Bağlı bir grafiğin minimum yayılma ağacı, ağaçtaki tüm kenarların ağırlıklarının toplamının en aza indirildiği , her tepe noktasını içeren bir ağacı oluşturan kenarların bir alt kümesidir . Bağlantısız bir grafik için minimum yayılma ormanıdır. her biri için ağaç kapsayan en az oluşan bağlı bileşenin .) Bu, a, algoritma olarak grafik teorisi bir oluşturmayan bir sonraki en düşük ağırlıklı kenar ekler her aşamada olduğu gibi döngüsü minimum yayılan orman.

Bu algoritma ilk olarak Proceedings of the American Mathematical Society , pp. 48–50'de 1956'da ortaya çıktı ve Joseph Kruskal tarafından yazılmıştır .

Bu problem için diğer algoritmalar arasında Prim'in algoritması , tersine silme algoritması ve Borůvka'nın algoritması bulunur .

Algoritma

• grafikteki her tepe noktasının ayrı bir ağaç olduğu bir orman F (bir dizi ağaç) oluşturun
• grafikteki tüm kenarları içeren bir S kümesi oluşturun
• iken S ise boş olmayan ve F henüz değil kapsayan
  • S'den minimum ağırlığa sahip bir kenarı kaldırın
  • kaldırılan kenar iki farklı ağacı birbirine bağlarsa, onu F ormanına ekleyin , iki ağacı tek bir ağaçta birleştirin

Algoritmanın sonlandırılmasında orman, grafiğin minimum genişleyen ormanını oluşturur. Grafik bağlıysa, ormanın tek bir bileşeni vardır ve minimum kapsayan bir ağaç oluşturur.

Sözde kod

Kruskal'ın algoritması için Öklid mesafesine dayalı ağırlıklarla eksiksiz bir grafik üzerinde bir demo .

Aşağıdaki kod, ayrık bir veri yapısı ile uygulanmaktadır . Burada, orman F'mizi bir kenarlar kümesi olarak temsil ediyoruz ve iki köşenin aynı ağacın parçası olup olmadığını verimli bir şekilde belirlemek için ayrık kümeli veri yapısını kullanıyoruz.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Karmaşıklık

E kenarları ve V köşeleri olan bir grafik için Kruskal'ın algoritmasının , tümü basit veri yapılarıyla O ( E log E ) zamanında veya eşdeğer olarak O ( E log V ) zamanında çalıştığı gösterilebilir . Bu çalışma süreleri eşdeğerdir çünkü:

• E en fazla ve . ${\ displaystyle V ^ {2}}$${\ displaystyle \ log V ^ {2} = 2 \ log V \, O (\ log V)}$
• İzole edilmiş her köşe, minimum yayılan ormanın ayrı bir bileşenidir. İzole köşeleri yok sayarsak, V ≤ 2 E elde ederiz , dolayısıyla log V olur . ${\ displaystyle O (\ log E)}$

Bu sınırı şu şekilde elde edebiliriz: ilk olarak kenarları , O ( E log E ) zamanında bir karşılaştırma sıralaması kullanarak ağırlığa göre sıralayın ; bu, " S'den minimum ağırlığa sahip bir kenarı kaldırma" adımının sabit zamanda çalışmasına izin verir . Daha sonra, hangi köşelerin hangi bileşenlerde olduğunu takip etmek için ayrık bir veri yapısı kullanıyoruz. Her tepe noktasını, O ( V ) işlemlerini alan kendi ayrık kümesine yerleştiriyoruz . Son olarak, en kötü durumda, tüm kenarları yinelemeliyiz ve her kenar için iki 'bul' işlemi ve muhtemelen bir birleşim yapmalıyız. Sıralamaya göre birleşimli ayrık kümeli ormanlar gibi basit bir ayrık kümeli veri yapısı bile O ( E log V ) zamanında O ( E ) işlemlerini gerçekleştirebilir . Böylece toplam süre O ( E log E ) = O ( E log V ) olur.

Kenarların önceden sıralanması veya doğrusal zamanda sıralanabilmesi koşuluyla (örneğin, sayma sıralaması veya taban sıralamasıyla ), algoritma O ( E α ( V )) zamanında çalışmak için daha karmaşık bir ayrık setli veri yapısı kullanabilir. α, tek değerli Ackermann fonksiyonunun son derece yavaş büyüyen tersidir .

Misal

Resim	Açıklama
	AD ve CE uzunluğu 5 ile, kısa kenarları vardır ve AD edilmiş keyfi vurgulamak için bir seçilen.
	CE artık 5 uzunluğuyla döngü oluşturmayan en kısa kenardır, bu nedenle ikinci kenar olarak vurgulanmıştır.
	Bir sonraki kenar, uzunluğu 6 olan DF , hemen hemen aynı yöntem kullanılarak vurgulanır.
	Sonraki en kısa kenarlar , her ikisi de 7 uzunluğunda olan AB ve BE'dir . AB keyfi olarak seçilir ve vurgulanır. BD kenarı kırmızıyla vurgulanmıştır, çünkü B ve D arasında zaten bir yol (yeşil) vardır , bu nedenle seçilmiş olsaydı bir döngü ( ABD ) oluştururdu.
	Süreç, bir sonraki en küçük kenarı, uzunluğu 7 olan BE'yi vurgulamaya devam eder . Bu aşamada daha birçok kenar kırmızı ile vurgulanır: BC , BCE döngüsünü oluşturacağı için , DE , DEBA döngüsünü oluşturacağı için ve FE, çünkü ŞUBAT formu .
	Son olarak, işlem uzunluğu 9 olan EG kenarı ile biter ve minimum kapsayan ağaç bulunur.

Doğruluğun kanıtı

İspat iki bölümden oluşmaktadır. İlk olarak, algoritmanın genişleyen bir ağaç ürettiği kanıtlanmıştır . İkincisi, inşa edilen yayılan ağacın minimum ağırlıkta olduğu kanıtlanmıştır.

Kapsayan ağaç

Let bağlı bir ağırlıklı grafik olabilir ve izin alt grafiği olarak algoritması tarafından üretilen. bir döngü ile sonuçlanırsa tanımı gereği bir kenar eklenmediği için bir döngü olamaz. İki bileşeni birleştiren ilk karşılaşılan kenar algoritma tarafından eklenmiş olacağından bağlantısı kesilemez. Böylece, yayılan bir ağaçtır . ${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle G}$

Minimum olma

Aşağıdaki P önermesinin tümevarımla doğru olduğunu gösteriyoruz : Eğer F , algoritmanın herhangi bir aşamasında seçilen kenarlar kümesiyse, o zaman F'yi içeren ve algoritma tarafından reddedilen kenarlardan hiçbiri olmayan bir minimum yayılma ağacı vardır .

• Açıkça P başlangıçta, F boşken doğrudur : herhangi bir minimum yayılma ağacı işe yarar ve bir tane vardır, çünkü ağırlıklı bağlı bir grafik her zaman minimum bir kapsama ağacına sahiptir.
• Şimdi , P'nin bazı son olmayan kenar kümeleri F için doğru olduğunu varsayalım ve T'yi , F'yi içeren bir minimum kapsayan ağaç olsun .
  • Bir sonraki seçilen kenar e de T içindeyse , o zaman P , F + e için doğrudur .
  • Aksi takdirde, e , T'de değilse, o zaman T + e'nin bir C döngüsü vardır . Bu döngü F'ye ait olmayan kenarları içerir , çünkü e , F'ye eklendiğinde bir döngü oluşturmaz, ancak T'de yapar . Let f olan bir kenar olabilir C de değil, F + e . Not f de aittir T , tarafından P algoritması tarafından kabul edilmemiştir. bu nedenle f , en az e kadar büyük bir ağırlığa sahip olmalıdır . O halde T - f + e bir ağaçtır ve T ile aynı veya daha az ağırlığa sahiptir . Yani T - f + E içeren bir minimum yayılan ağaç F + e ve tekrar P tutar.
• Bu nedenle, tümevarım ilkesine göre, P , F bir kapsayan ağaç haline geldiğinde, ancak F'nin minimum kapsayan bir ağacın kendisi olması durumunda mümkündür .

Paralel algoritma

Kruskal'ın algoritması doğası gereği sıralıdır ve paralelleştirilmesi zordur. Bununla birlikte, kenarların ilk sınıflandırmasını paralel olarak gerçekleştirmek veya alternatif olarak, her yinelemede minimum ağırlıklı kenarı çıkarmak için bir ikili yığının paralel bir uygulamasını kullanmak mümkündür . Paralel sıralama sürede mümkün olduğu gibi ilgili işlemci, Kruskal algoritması çalışma süresi azaltılabilir O ( e α ( V α yine tek değerli tersidir)), Ackermann fonksiyonu . ${\ displaystyle O (n)}$${\ displaystyle O (\ log n)}$

Kruskal algoritmasının Filter-Kruskal adlı bir varyantı, Osipov ve ark. ve paralelleştirme için daha uygundur. Filter-Kruskal'ın arkasındaki temel fikir , ayırma maliyetini düşürmek için aynı ağacın köşelerini birbirine bağlayan kenarları hızlı sıralama ve filtrelemeye benzer şekilde kenarları bölümlere ayırmaktır . Aşağıdaki sözde kod bunu göstermektedir.

function filter_kruskal(G) is
    if |G.E| < kruskal_threshold:
        return kruskal(G)
    pivot = choose_random(G.E)
    ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$ = partition(G.E, pivot)
    A = filter_kruskal(${\displaystyle E_{\leq }}$)
    ${\displaystyle E_{>}}$ = filter(${\displaystyle E_{>}}$)
    A = A ∪ filter_kruskal(${\displaystyle E_{>}}$)
    return A

function partition(E, pivot) is
    ${\displaystyle E_{\leq }}$ = ∅, ${\displaystyle E_{>}}$ = ∅
    foreach (u, v) in E do
        if weight(u, v) <= pivot then
            ${\displaystyle E_{\leq }}$ = ${\displaystyle E_{\leq }}$ ∪ {(u, v)}
        else
            ${\displaystyle E_{>}}$ = ${\displaystyle E_{>}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$

function filter(E) is
    ${\displaystyle E_{\text{filtered}}}$ = ∅
    foreach (u, v) in E do
        if find_set(u) ≠ find_set(v) then
            ${\displaystyle E_{\text{filtered}}}$ = ${\displaystyle E_{\text{filtered}}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\text{filtered}}}$

Filtreleme, filtreleme ve bölümleme işlemciler arasında kenarları dağıtarak paralel olarak kolayca gerçekleştirilebildiğinden, Filter-Kruskal paralelleştirme için daha iyi bir avantaj sağlar.

Son olarak, Kruskal algoritmasının paralel uygulamasının diğer varyantları araştırılmıştır. Örnekler arasında, arka planda kesinlikle MST'nin parçası olmayan kenarları kaldırmak için yardımcı iş parçacıkları kullanan bir şema ve sıralı algoritmayı p alt grafiklerinde çalıştıran, ardından bu alt grafikleri yalnızca biri olan son MST kalana kadar birleştiren bir varyant yer alır .

Ayrıca bakınız

• Prim'in algoritması
• Dijkstra algoritması
• Borůvka algoritması
• Ters silme algoritması
• Tek bağlantılı kümeleme
• Açgözlü geometrik anahtar

Referanslar

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein . Algoritmalara Giriş , İkinci Baskı. MIT Press ve McGraw-Hill, 2001. ISBN   0-262-03293-7 . Bölüm 23.2: Kruskal ve Prim'in algoritmaları, s. 567–574.
• Michael T. Goodrich ve Roberto Tamassia . Java'da Veri Yapıları ve Algoritmalar , Dördüncü Baskı. John Wiley & Sons, Inc., 2006. ISBN   0-471-73884-0 . Bölüm 13.7.1: Kruskal Algoritması, s. 632 ..

Dış bağlantılar

• Makalenin örneği için veriler .
• Minimum Yayılma Ağacı kaynak kodunu Hesaplamak İçin Gephi Eklentisi .
• C ++ 'da örnek ve programla Kruskal Algoritması
• Rastgele sayılara uygulanan C ++ 'da Kruskal'ın Algoritma kodu
• Kruskal'ın Python'daki algoritma kodu açıklamalı