Bir graph’taki her bir vertex’i her vertex arasında bir yol olacak şekilde en ucuz maliyetle birbirine bağlanmasına minumum spanning tree denir.
Minumum spanning tree’de kenarların toplam ağırlığı minimum olması gereklidir. Graph’ın tüm vertexler’lerini birbirine bağlamalıdır. Ayrıca herhangi bir döngü bulunmamalıdır.
Minumum spanning tree’de en yaygın kullanılan algoritmalar:
- Prim’s Algorithm
- Kruskal Algorithm
dır.
Prim’s Algorithm
İlk olarak, varsa graph’da paralel olan kenarlardan en maliyetli olanlar ve döngüler (kendine giden kenarlar) atılır.
Başlangıç düğümü belirlenir.
Ziyaret edilmemiş kenarlar ve vertex’ler belirlenir. Başlangıç vertex’iyle bağlantılı olan tüm kenarlar incelenir ve en maliyetsiz kenarla ziyaret edilmemiş vertex’e gidilir. Eğer eşit maliyetle vertex varsa içlerinden biri seçilir. Vertex ağaca eklenir. Bu işlem tüm vertex’ler ağaca eklenene kadar devam eder. N adet vertex için N-1 kez işlem tekrarlanacaktır.
Aşağıdaki graph için Prim’s Algoritmasını kullanarak minimum spanning tree oluşturalım.
Başlangıç düğümümüz A olsun. A’yla bağlantılı olan 2 vertex var ve ikisinin de maliyeti eşit. B’ye gideni seçelim. O kenarla vertex’i ağaca ekleyelim. Vertex’i ziyaret edildi olarak işaretleyelim.
Şimdi ise başlangıç vertex’iyle bağlantılı 1 ve 3 kenarları var. Bunlardan en maliyetsiz olan 1 kenarını seçelim ve bağlı olduğu vertex ile ağaca ekleyelim. Vertex’i ziyaret edildi olarak işaretleyelim.
Başlangıç vertex’iyle bağlantılı 3 ve 5 kenarları var. Bu kenarlardan en maliyetsiz olan 3 kenarını seçelim. Bağlı olduğu vertex ile ağace ekleyelim. Vertex’i ziyaret edidli olarak işaretleyelim.
Başlangıç vertex’iyle bağlantılı 2 ve 5 kenarları var. En maliyetsiz olan 2 kenarını seçelim ve bağlı olduğu vertex’le birlikte ağaca ekleyeyip ziyaret edildi olarak işaretleyelim.
Böylelikle tüm vertex’leri 5-1 = 4 tekrar ile ağaca ekleyerek minimum spanning tree’yi oluşturduk.
Kruskal Algorithm
İlk olarak graph’daki tüm kenarlar küçükten büyüğe sıralanır. En küçük kenardan başlanarak ağaç oluşturulur. Eklenecek kenar eğer ağaçta cycle (döngü) oluşturuyorsa o kenar ağaca eklenmez. Tüm vertex’ler ağaca eklendiğinde işlem sonlanır.
Aşağıdaki graph için Kruskal Algoritmasını kullanarak minimum spanning tree oluşturalım.
İlk olarak tüm kenarları küçükten büyüğe sıralayalım.
En küçük kenardan başlayarak ağacı oluşturmaya başlayalım.
Tüm vertex’ler ağaca eklendiği için işlem tamamlandı ve minimum spanning tree oluştu.