DAA - Genişleyen Ağaç

Bir spanning tree Tüm köşeleri minimum sayıda kenarla birbirine bağlayan yönsüz bir Grafiğin bir alt kümesidir.

Tüm köşeler bir grafiğe bağlıysa, en az bir kapsayan ağaç vardır. Bir grafikte birden fazla yayılan ağaç olabilir.

Özellikleri

• Kapsayan bir ağacın herhangi bir döngüsü yoktur.
• Herhangi bir tepe noktasına başka herhangi bir tepe noktasından ulaşılabilir.

Misal

Aşağıdaki grafikte, vurgulanan kenarlar bir kapsayan ağaç oluşturur.

Az yer kaplayan ağaç

Bir Minimum Spanning Tree (MST)tüm köşeleri mümkün olan minimum toplam kenar ağırlığıyla birbirine bağlayan bağlı ağırlıklı yönsüz grafiğin kenarlarının bir alt kümesidir. Bir MST türetmek için Prim'in algoritması veya Kruskal'ın algoritması kullanılabilir. Bu nedenle, Prim'in algoritmasını bu bölümde tartışacağız.

Tartıştığımız gibi, bir grafiğin birden fazla kapsayan ağacı olabilir. Eğer varsan köşe sayısı, kapsayan ağacın sahip olması gerekir n - 1kenar sayısı. Bu bağlamda, grafiğin her kenarı bir ağırlıkla ilişkilendirilmişse ve birden fazla yayılan ağaç varsa, grafiğin minimum kapsayan ağacını bulmamız gerekir.

Ayrıca, herhangi bir kopya ağırlıklı kenar varsa, grafik birden fazla minimum yayılma ağacına sahip olabilir.

Yukarıdaki grafikte, minimum kapsayan ağaç olmasa da bir kapsayan ağaç gösterdik. Bu genişleyen ağacın maliyeti (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38'dir.

Minimum yayılma ağacını bulmak için Prim'in algoritmasını kullanacağız.

Prim Algoritması

Prim'in algoritması, minimum yayılma ağacını bulmak için açgözlü bir yaklaşımdır. Bu algoritmada, bir MST oluşturmak için keyfi bir tepe noktasından başlayabiliriz.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Ayıkla-Min işlevi, minimum kenar maliyetiyle tepe noktasını döndürür. Bu işlev min-heap üzerinde çalışır.

Misal

Prim'in algoritmasını kullanarak herhangi bir tepe noktasından başlayabiliriz, tepe noktasından başlayalım 1.

Köşe 3 tepe noktasına bağlı 1 minimum kenar maliyetiyle, dolayısıyla kenar (1, 2) kapsayan ağaca eklenir.

Sonra, kenar (2, 3) bu, kenarlar arasında minimum olduğu için {(1, 2), (2, 3), (3, 4), (3, 7)}.

Bir sonraki adımda avantaj elde ederiz (3, 4) ve (2, 4)minimum maliyetle. Kenar(3, 4) rastgele seçilir.

Benzer şekilde, kenarlar (4, 5), (5, 7), (7, 8), (6, 8) ve (6, 9)seçildi. Tüm köşeler ziyaret edildiğinde artık algoritma durur.

Kapsayan ağacın maliyeti (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23'tür. Bu grafikte daha düşük maliyetli yayılan ağaç yoktur. 23.