Kruskals algoritması - Kruskals algorithm - Wikipedia

Kruskal'ın algoritması bulur minimum genişleyen orman yönsüz kenar ağırlıklı grafik. Grafik ise bağlı, bulur az yer kaplayan ağaç. (Bağlı bir grafiğin minimum kapsama ağacı, kenarlar her şeyi içeren bir ağaç oluşturan tepe toplamı nerede ağırlıklar ağaçtaki tüm kenarların küçültülmesi. Bağlantısız bir grafik için, minimum yayılan orman, her biri için minimum bir kapsayan ağaçtan oluşur. bağlı bileşen.) Bu bir Açgözlü algoritma içinde grafik teorisi her adımda olduğu gibi, bir sonraki en düşük ağırlıklı kenarı ekler döngü minimum yayılan ormana.^[1]

Bu algoritma ilk olarak American Mathematical Society'nin Bildirileri, pp. 48–50, 1956'da yazılmıştır. Joseph Kruskal.^[2]

Bu problem için diğer algoritmalar şunları içerir: Prim'in algoritması, tersine silme algoritması, ve Borůvka algoritması.

Algoritma

bir orman yarat F (bir dizi ağaç), burada grafikteki her tepe noktası ayrıdır ağaç
bir set oluştur S grafikteki tüm kenarları içeren
süre S dır-dir boş değil ve F henüz değil kapsayan
- minimum ağırlıkta bir kenarı kaldırın S
- kaldırılan kenar iki farklı ağacı birleştirirse ormana ekleyin F, iki ağacı tek bir ağaçta birleştirmek

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 bir demo tam grafik Öklid mesafesine dayalı ağırlıklarla.

Aşağıdaki kod, bir ayrık kümeli veri yapısı. Burada ormanımızı temsil ediyoruz F bir dizi kenar olarak kullanın ve iki köşenin aynı ağacın parçası olup olmadığını verimli bir şekilde belirlemek için ayrık veri yapısını kullanın.

algoritma Kruskal (G) dır-dir    F: = ∅ her biri için v ∈ G.V yapmak        MAKE-SET (v) her biri için (u, v) içinde G.E ağırlığa göre sıralı (u, v), artan yapmak        Eğer BUL-AYARI (u) ≠ BUL-AYARI (v) sonra            F: = F ∪ {(u, v)} BİRLİĞİ (BUL-KÜMESİ (u), BUL-KÜMESİ (v)) dönüş F

Karmaşıklık

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

E en fazla ${ displaystyle V ^ {2}}$ ve ${ displaystyle log V ^ {2} = 2 log V , O ( log V)}$ .
İzole edilmiş her tepe noktası, minimum yayılan ormanın ayrı bir bileşenidir. İzole köşeleri görmezden gelirsek elde ederiz V ≤ 2Eöyleyse günlük V dır-dir ${ displaystyle O ( log E)}$ .

Bu sınırı şu şekilde elde edebiliriz: ilk olarak kenarları a kullanarak ağırlığa göre sıralayabiliriz. karşılaştırma sıralaması içinde Ö(E günlük E) zaman; bu, "minimum ağırlıkta bir kenarı kaldırma adımına izin verir S"sabit zamanda çalışmak için. Daha sonra, bir ayrık kümeli veri yapısı hangi bileşenlerin hangi köşelerde olduğunu takip etmek için. Her köşe noktasını, O (V) operasyonlar. 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şen ayrık kümeli ormanlar gibi basit bir ayrık kümeli veri yapısı bile O (E) operasyonlar Ö(E günlük V) zaman. Böylece toplam süre Ö(E günlük E) = Ö(E günlük V).

Kenarların ya önceden sıralanmış olması ya da doğrusal zamanda sıralanabilmesi koşuluyla (örneğin sayma sıralaması veya radix sıralama ), algoritma daha karmaşık bir ayrık kümeli veri yapısı koşmak Ö(E α (V)) zaman, burada α tek değerli olanın son derece yavaş büyüyen tersi Ackermann işlevi.

Misal

Resim	Açıklama
	AD ve CE 5 uzunluğunda en kısa kenarlardır ve AD olmuştur keyfi olarak seçildiğinden vurgulanır.
	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, DF 6 uzunluğunda, hemen hemen aynı yöntem kullanılarak vurgulanır.
	Sonraki en kısa kenarlar AB ve BEher ikisi de 7 uzunluğunda. AB keyfi olarak seçilir ve vurgulanır. Kenar BD kırmızıyla vurgulanmıştır, çünkü arasında zaten bir yol (yeşil) vardır. B ve D, böylece bir döngü oluşturacaktır (ABD) eğer seçilmişse.
	Süreç, bir sonraki en küçük kenarı vurgulamaya devam ediyor, BE 7 uzunluğundadır. Bu aşamada daha birçok kenar kırmızıyla vurgulanır: M.Ö çünkü döngüyü oluşturacaktı MÖ, DE çünkü döngüyü oluşturacaktı DEBA, ve FE çünkü oluşacak ŞUBAT.
	Son olarak işlem kenar ile biter ÖRNEĞİN uzunluğu 9 ve minimum kapsayan ağaç bulunur.

Doğruluğun kanıtı

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

Kapsayan ağaç

İzin Vermek ${ displaystyle G}$ bağlantılı, ağırlıklı bir grafik olun ve ${ displaystyle Y}$ alt grafiği olmak ${ displaystyle G}$ algoritma tarafından üretilir. ${ displaystyle Y}$ bir döngü ile sonuçlanırsa tanımı gereği bir kenar eklenmediği için bir döngü olamaz. ${ displaystyle Y}$ iki bileşeni birleştiren ilk karşılaşılan kenar olduğundan bağlantısı kesilemez ${ displaystyle Y}$ algoritma tarafından eklenmiş olurdu. Böylece, ${ displaystyle Y}$ yayılan ağaç ${ displaystyle G}$ .

Minimum olma

Aşağıdaki önerinin P doğru indüksiyon: Eğer F Algoritmanın herhangi bir aşamasında seçilen kenarlar kümesidir, bu durumda aşağıdakileri içeren bir minimum yayılma ağacı vardır: F ve algoritma tarafından reddedilen kenarların hiçbiri.

Açıkça P başlangıçta doğrudur, ne zaman F boş: herhangi bir minimum yayılan ağaç işe yarar ve bir tane vardır çünkü ağırlıklı bağlantılı bir grafik her zaman minimum bir kapsayan ağaçlara sahiptir.
Şimdi varsayalım P bazı nihai olmayan kenar kümeleri için doğrudur F ve izin ver T içeren minimum yayılan ağaç olmak F.
- Bir sonraki seçilen kenar e ayrıca içinde T, sonra P için doğru F + e.
- Aksi takdirde, eğer e içinde değil T sonra T + e bir döngüsü var C. Bu döngü, ait olmayan kenarları içerir. F, dan beri e eklendiğinde bir döngü oluşturmaz F ama içinde T. İzin Vermek f içinde olan bir kenar olmak C ama içinde değil F + e. Bunu not et f ayrıca aittir Tve tarafından P algoritma tarafından dikkate alınmamıştır. f bu nedenle en az şu kadar büyük olmalıdır: e. Sonra T − f + e bir ağaçtır ve aynı veya daha az ağırlığa sahiptir. T. Yani T − f + e içeren minimum yayılan ağaçtır F + e ve yeniden P tutar.
Bu nedenle, indüksiyon prensibi ile, P ne zaman tutar F yayılan bir ağaç haline geldi, bu yalnızca mümkünse F minimum yayılan ağacın kendisidir.

Paralel algoritma

Kruskal'ın algoritması doğası gereği sıralıdır ve paralelleştirilmesi zordur. Bununla birlikte, kenarların ilk tasnifini paralel olarak gerçekleştirmek veya alternatif olarak, bir paralel uygulamasının kullanılması mümkündür. ikili yığın her yinelemede minimum ağırlık kenarını çıkarmak için.^[3]Zamanla paralel sıralama mümkün olduğundan ${ displaystyle O (n)}$ açık ${ displaystyle O ( log n)}$ işlemciler,^[4] Kruskal'ın algoritmasının çalışma süresi azaltılabilir Ö(E α (V)), burada α yine tek değerli olanın tersidir Ackermann işlevi.

Kruskal algoritmasının Filter-Kruskal adlı bir varyantı, Osipov ve diğerleri tarafından açıklanmıştır.^[5] ve paralelleştirme için daha uygundur. Filter-Kruskal'ın arkasındaki temel fikir, kenarları benzer şekilde bölmektir. hızlı sıralama ve sıralama maliyetini azaltmak için aynı ağacın köşelerini birbirine bağlayan kenarları filtreleyin. Aşağıdaki sözde kod bunu gösteriyor.

işlevi filter_kruskal (G) dır-dir    Eğer | G.E | dönüş kruskal (G) pivot = random_seçim (G.E)  ${ displaystyle E _ {<=}}$ ,  ${ displaystyle E _ {>}}$  = bölüm (G.E, pivot) A = filter_kruskal ( ${ displaystyle E _ {<=}}$ )     ${ displaystyle E _ {>}}$  = filtre ( ${ displaystyle E _ {>}}$ ) A = A ∪ filter_kruskal ( ${ displaystyle E _ {>}}$ )    dönüş Birişlevi bölüm (E, pivot) dır-dir     ${ displaystyle E _ {<=}}$  = ∅,  ${ displaystyle E _ {>}}$  = ∅    her biri için (u, v) E içinde yapmak        Eğer ağırlık (u, v) <= pivot sonra             ${ displaystyle E _ {<=}}$  =  ${ displaystyle E _ {<=}}$  ∪ {(u, v)} Başka             ${ displaystyle E _ {>}}$  =  ${ displaystyle E _ {>}}$  ∪ {(u, v)} dönüş  ${ displaystyle E _ {<=}}$ ,  ${ displaystyle E _ {>}}$ işlevi filtre (E) dır-dir     ${ displaystyle E_ {filtrelenmiş}}$  = ∅    her biri için (u, v) E içinde yapmak        Eğer bul_kümesi (u) ≠ bul_kümesi (v) sonra             ${ displaystyle E_ {filtrelenmiş}}$  =  ${ displaystyle E_ {filtrelenmiş}}$  ∪ {(u, v)} dönüş  ${ displaystyle E_ {filtrelenmiş}}$

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

Son olarak, Kruskal algoritmasının paralel uygulamasının diğer varyantları araştırıldı. Örnekler, arka planda kesinlikle MST'nin parçası olmayan kenarları kaldırmak için yardımcı dişler kullanan bir şema,^[6] ve sıralı algoritmayı çalıştıran bir varyant p alt grafikler, daha sonra yalnızca biri olan son MST kalana kadar bu alt grafikleri birleştirir.^[7]

Ayrıca bakınız

Referanslar

^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein (2009). Algoritmalara Giriş (Üçüncü baskı). MIT Basın. pp.631. ISBN 978-0262258104.CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)
^ Kruskal, J. B. (1956). "Bir grafiğin en kısa kapsama alt ağacında ve seyyar satıcı probleminde". American Mathematical Society'nin Bildirileri. 7 (1): 48–50. doi:10.1090 / S0002-9939-1956-0078686-7. JSTOR 2033241.
^ Quinn, Michael J .; Deo, Narsingh (1984). "Paralel grafik algoritmaları". ACM Hesaplama Anketleri. 16 (3): 319–348. doi:10.1145/2514.2515.
^ Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003). Paralel Hesaplamaya Giriş. sayfa 412–413. ISBN 978-0201648652.
^ ^a ^b Osipov, Vitaly; Sanders, Peter; Şarkıcı, Johannes (2009). "Filtre-kruskal minimum yayılma ağacı algoritması" (PDF). Algoritma Mühendisliği ve Deneyleri Onbirinci Çalıştayı Bildirileri (ALENEX). Endüstriyel ve Uygulamalı Matematik Derneği: 52–61.
^ Katsigiannis, Anastasios; Anastopoulos, Nikos; Konstantinos, Nikas; Koziris, Nectarios (2012). "Kruskal algoritmasını yardımcı iş parçacıkları kullanarak paralel hale getirmek için bir yaklaşım" (PDF). Paralel ve Dağıtık İşleme Sempozyumu Çalıştayları ve PHD Forumu (IPDPSW), 2012 IEEE 26th International: 1601–1610.
^ Lončar, Vladimir; Škrbić, Srdjan; Balaž, Antun (2014). "Dağıtılmış Bellek Mimarileri Kullanılarak Minimum Yayılma Ağacı Algoritmalarının Paralelleştirilmesi". Mühendislik Teknolojileri ile İlgili İşlemler.: 543–554.

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

[:0-1] Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein (2009). Algoritmalara Giriş (Üçüncü baskı). MIT Basın. pp.631. ISBN 978-0262258104.CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)

[2] Kruskal, J. B. (1956). "Bir grafiğin en kısa kapsama alt ağacında ve seyyar satıcı probleminde". American Mathematical Society'nin Bildirileri. 7 (1): 48–50. doi:10.1090 / S0002-9939-1956-0078686-7. JSTOR 2033241.

[3] Quinn, Michael J .; Deo, Narsingh (1984). "Paralel grafik algoritmaları". ACM Hesaplama Anketleri. 16 (3): 319–348. doi:10.1145/2514.2515.

[4] Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003). Paralel Hesaplamaya Giriş. sayfa 412–413. ISBN 978-0201648652.

[osipov2009-5] Osipov, Vitaly; Sanders, Peter; Şarkıcı, Johannes (2009). "Filtre-kruskal minimum yayılma ağacı algoritması" (PDF). Algoritma Mühendisliği ve Deneyleri Onbirinci Çalıştayı Bildirileri (ALENEX). Endüstriyel ve Uygulamalı Matematik Derneği: 52–61.

[6] Katsigiannis, Anastasios; Anastopoulos, Nikos; Konstantinos, Nikas; Koziris, Nectarios (2012). "Kruskal algoritmasını yardımcı iş parçacıkları kullanarak paralel hale getirmek için bir yaklaşım" (PDF). Paralel ve Dağıtık İşleme Sempozyumu Çalıştayları ve PHD Forumu (IPDPSW), 2012 IEEE 26th International: 1601–1610.

[7] Lončar, Vladimir; Škrbić, Srdjan; Balaž, Antun (2014). "Dağıtılmış Bellek Mimarileri Kullanılarak Minimum Yayılma Ağacı Algoritmalarının Paralelleştirilmesi". Mühendislik Teknolojileri ile İlgili İşlemler.: 543–554.

[1]

[2]

[3]

[4]

[5]

[6]

[7]