Borůvka'nın algoritması - Borůvka's algorithm

Boruvka'nın algoritmasının animasyonu

Borůvka'nın algoritması , bir grafikte minimum yayılan ağacı veya bağlı olmayan bir grafik durumunda minimum yayılan ormanı bulmak için açgözlü bir algoritmadır .

İlk olarak 1926'da Otakar Borůvka tarafından Moravya için verimli bir elektrik şebekesi kurma yöntemi olarak yayınlandı . Algoritma 1938'de Choquet tarafından yeniden keşfedildi ; 1951'de yine Florek , Łukasiewicz , Perkal , Steinhaus ve Zubrzycki tarafından; ve yine 1965'te Georges Sollin tarafından. Bu algoritma , özellikle paralel hesaplama literatüründe sıklıkla Sollin'in algoritması olarak adlandırılır .

Algoritma, grafiğin her köşesine minimum ağırlıklı kenar olayı bularak ve bu kenarların tümünü ormana ekleyerek başlar. Ardından, şimdiye kadar oluşturulmuş her ağaçtan farklı bir ağaca minimum ağırlık kenarını bulmak ve bu kenarların hepsini ormana eklemek için benzer bir işlemi tekrarlar. Bu işlemin her tekrarı, grafiğin her bağlantılı bileşeni içindeki ağaç sayısını bu eski değerin en fazla yarısına düşürür, böylece logaritmik olarak birçok tekrardan sonra işlem tamamlanır. Bunu yaptığında, eklediği kenar kümesi minimum yayılan ormanı oluşturur.

sözde kod

Aşağıdaki sözde kod, Borůvka'nın algoritmasının temel bir uygulamasını göstermektedir. Koşullu maddelerde, her kenar uv "Yok" tan daha ucuz olarak kabul edilir. Tamamlanan değişkenin amacı, F ormanının henüz yayılan bir orman olup olmadığını belirlemektir .

Kenarların farklı ağırlıkları yoksa , örneğin köşeler veya kenarlar üzerindeki bazı toplam sıraya dayalı olarak tutarlı bir eşitlik bozma kuralı kullanılmalıdır . Bu, köşeleri tamsayılar olarak temsil ederek ve bunları doğrudan karşılaştırarak başarılabilir; bellek adreslerini karşılaştırma ; vb. Oluşturulan grafiğin gerçekten bir orman olduğundan, yani döngü içermediğinden emin olmak için bir bağ-kırma kuralı gereklidir. Örneğin, { a , b , c } düğümleri ve ağırlık 1'in tüm kenarlarına sahip bir üçgen grafiği düşünün . O zaman , { a } için minimum ağırlık kenarı olarak ab , { b } için bc'yi seçersek bir döngü oluşturulabilir ve ca { c } için. Kenarları önce kaynağa, sonra hedefe göre sıralayan bir bağlantı koparma kuralı, bir döngü oluşturulmasını önleyerek minimum yayılan ağaç { ab , bc } ile sonuçlanır .

algorithm Borůvka is
    input: A weighted undirected graph G = (V, E).
    output: F, a minimum spanning forest of G.

    Initialize a forest F to (V, E') where E' = {}.

    completed := false
    while not completed do
        Find the connected components of F and assign to each vertex its component
        Initialize the cheapest edge for each component to "None"
        for each edge uv in E, where u and v are in different components of F:
            let wx be the cheapest edge for the component of u
            if is-preferred-over(uv, wx) then
                Set uv as the cheapest edge for the component of u
            let yz be the cheapest edge for the component of v
            if is-preferred-over(uv, yz) then
                Set uv as the cheapest edge for the component of v
        if all components have cheapest edge set to "None" then
            // no more trees can be merged -- we are finished
            completed := true
        else
            completed := false
            for each component whose cheapest edge is not "None" do
                Add its cheapest edge to E'

function is-preferred-over(edge1, edge2) is
    return (edge1 is "None") or
           (weight(edge1) < weight(edge2)) or
           (weight(edge1) = weight(edge2) and tie-breaking-rule(edge1, edge2))

function tie-breaking-rule(edge1, edge2) is
    The tie-breaking rule; returns true if and only if edge1
    is preferred over edge2 in the case of a tie.

Bir optimizasyon olarak, aynı bileşende iki köşeyi birbirine bağladığı bulunan her kenar G'den çıkarılabilir , böylece sonraki bileşenlerde en ucuz kenarları arama zamanına katkıda bulunmaz.

karmaşıklık

Borůvka'nın algoritmasının, sonlanana kadar dış döngünün O (log V ) yinelemelerini aldığı ve dolayısıyla O ( E log V ) zamanında çalıştığı gösterilebilir ; burada E , kenarların sayısıdır ve V , içindeki köşelerin sayısıdır. G ( EV varsayılarak ). Olarak düzlemsel grafikler ve daha genel olarak altında kapalı grafikler ailelerinde grafik minör işlemleri, algoritmanın her aşamadan sonra bileşenlerin her biri arasında tüm ama en ucuz kenarı kaldırarak, lineer zamanda çalışacak şekilde yapılabilir.

Misal

resim bileşenler Açıklama
Borůvka Algoritması 1.svg {A}
{B}
{C}
{D}
{E}
{F}
{G}
Bu bizim orijinal ağırlıklı grafiğimizdir. Kenarlara yakın sayılar ağırlıklarını gösterir. Başlangıçta her köşe kendi başına bir bileşendir (mavi daireler).
Borůvka Algoritması 2.svg {A,B,D,F}
{C,E,G}
Dış döngünün ilk yinelemesinde, her bileşenin minimum ağırlık kenarı eklenir. Bazı kenarlar iki kez seçilir (AD, CE). İki bileşen kaldı.
Borůvka Algoritması 3.svg {A,B,C,D,E,F,G} İkinci ve son yinelemede, kalan iki bileşenin her birinin minimum ağırlık kenarı eklenir. Bunlar aynı kenar olur. Bir bileşen kaldı ve işimiz bitti. Her iki uç nokta da aynı bileşende olduğu için BD kenarı dikkate alınmaz.

Diğer algoritmalar

Bu problem için diğer algoritmalar Prim'in algoritmasını ve Kruskal'ın algoritmasını içerir . Prim'in algoritması ile Borůvka'nın algoritmasını birleştirerek hızlı paralel algoritmalar elde edilebilir.

Karger, Klein ve Tarjan nedeniyle kısmen Borůvka'nın algoritmasına dayanan daha hızlı bir rastgele minimum yayılan ağaç algoritması, beklenen O( E ) zamanında çalışır. Bernard Chazelle tarafından en iyi bilinen (deterministik) minimum yayılan ağaç algoritması da kısmen Borůvka'ya dayanmaktadır ve O( E α( E , V )) zamanında çalışır, burada α, Ackermann fonksiyonunun tersidir . Bu rastgele ve deterministik algoritmalar, Borůvka'nın algoritmasının adımlarını birleştirerek, kalan bileşenlerin sayısını azaltarak, bileşen çiftleri arasındaki kenar sayısını azaltan farklı türdeki adımlarla birleştirir.

Notlar

  1. ^ Borůvka, Otakar (1926). "O jistém problému minimálním" [Belirli bir minimal sorun hakkında]. Práce Mor. Přírodověd. Spol. V Brně III (Çekçe ve Almanca). 3 : 37-58.
  2. ^ Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (elektrik şebekelerinin ekonomik inşaatı sorununun çözümüne katkı)". Elektronický Obzor (Çekçe). 15 : 153-154.
  3. ^ Nešetřil, Jaroslav ; Milkova, Eva; Neşetřilová, Helena (2001). "Asgari kapsayan ağaç sorunu üzerine Otakar Borůvka: 1926 kağıtların, yorumların, tarihin her ikisinin de çevirisi". Ayrık Matematik . 233 (1-3): 3-36. doi : 10.1016/S0012-365X(00)00224-7 . hdl : 10338.dmlcz/500413 . MR  1825599 .
  4. ^ Choquet, Gustave (1938). "Etude de belirli réseaux de yolları". Comptes Rendus de l'Académie des Sciences (Fransızca). 206 : 310-313.
  5. ^ Florek, K.; Łukaszewicz, J .; Perkal, J.; Steinhaus, Hugo ; Zubrzycki, S. (1951). "Sur la liison et la Division des Points d'un Ensemble Fini" . Colloquium Mathematicae (Fransızca). 2 : 282–285. MR  0048832 .
  6. ^ Sollin, Georges (1965). "Le trace de kanalizasyon". Programlama, Oyunlar ve Ulaşım Ağları (Fransızca).
  7. ^ Eppstein, David (1999). "Ağaçları ve anahtarları kapsayan". In Sack, J.-R. ; Urrutia, J. (ed.). Hesaplamalı Geometri El Kitabı . Elsevier. s. 425-461.; Mareş, Martin (2004). "Minör kapalı grafik sınıflarında MST için iki doğrusal zaman algoritması" (PDF) . Archivum Mathematicum . 40 (3): 315–320..
  8. ^ Bader, David A.; Cong, Guojing (2006). "Nadir grafiklerin minimum yayılan ormanını hesaplamak için hızlı paylaşılan bellek algoritmaları". Paralel ve Dağıtılmış Hesaplama Dergisi . 66 (11): 1366-1378. CiteSeerX  10.1.1.129.8991 . doi : 10.1016/j.jpdc.2006.06.001 .
  9. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "Minimum yayılan ağaçları bulmak için rastgele doğrusal zaman algoritması". ACM Dergisi . 42 (2): 321–328. CiteSeerX  10.1.1.39.9012 . doi : 10.1145/201019.201022 .
  10. ^ Chazelle, Bernard (2000). "Ters Ackermann tipi karmaşıklığa sahip minimum yayılan ağaç algoritması" (PDF) . J. ACM . 47 (6): 1028–1047. CiteSeerX  10.1.1.115.2318 . doi : 10.1145/355541.355562 .