minimum spanning tree tutorial
Bu C ++ Eğiticisi, Bir Grafikte MST'yi Bulmak İçin Prim ve Kruskal Algoritmalarının yanı sıra Minimum Genişleme Ağacının (MST) Ne Olduğunu Açıklar:
Yayılan ağaç, minimum olası kenarları kapsayan tüm köşelerden oluşan ve bir döngüye sahip olmayan bir grafiğin bir alt kümesi olarak tanımlanabilir. Yayılma ağacının bağlantısı kesilemez.
Her bağlantılı ve yönlendirilmemiş grafiğin en az bir kapsayan ağacı vardır. Tüm köşeleri dahil etmek mümkün olmadığından, bağlantısı kesilmiş bir grafiğin kapsayan bir ağacı yoktur.
=> Tam C ++ Öğreticiler listesini Keşfetmek İçin Buraya Bakın.
Ne öğreneceksin:
C ++ 'da Genişleyen Ağaç
Aşağıdaki bağlantılı grafiği düşünün.
Yukarıda gösterildiği gibi, 3 köşe içeren verilen bağlantılı Grafik için, üç uzanan ağaca sahibiz. Genel olarak, N bir grafikteki düğüm sayısı ise, tam bir bağlı grafik maksimum N'ye sahiptir.N-2yayılan ağaçların sayısı. Dolayısıyla yukarıdaki grafikte N = 3, dolayısıyla 3(3-2)= 3 uzanan ağaç.
Kapsayan ağacın bazı özellikleri aşağıda listelenmiştir:
- Bağlı bir grafiğin birden fazla kapsayan ağacı olabilir.
- Bir grafikteki tüm yayılan ağaçların aynı sayıda düğümü ve kenarı vardır.
- Kapsayan ağaçtan bir kenarı kaldırırsak, o zaman minimum bağlı ve grafiğin bağlantısını kesecek.
- Öte yandan, kapsayan ağaca bir kenar eklemek onu azami döngüsel olmayan böylece bir döngü oluşturur.
- Kapsayan bir ağacın bir döngüsü veya döngüsü yoktur.
Minimum Genişleme Ağacı Nedir (MST)
Minimum yayılan ağaç, bağlantılı bir ağırlıklı grafiğin diğer tüm kapsayan ağaçları arasında en az ağırlığı içeren ağaçtır. Bir grafik için birden fazla minimum kapsayan ağaç olabilir.
Bir grafikte minimum yayılma ağacını bulmak için kullanılan en popüler iki algoritma vardır.
Onlar içerir:
- Kruskal'ın algoritması
- Prim'in algoritması
Şimdi bu iki algoritmayı da tartışalım!
Kruskal Algoritması
Kruskal'ın algoritması, MST'yi bağlantılı bir grafikte bulmaya yönelik bir algoritmadır.
Kruskal’ın algoritması, aşağıdaki şekilde bir G grafiğinin alt kümesini bulur:
- İçindeki her tepe noktasıyla bir ağaç oluşturur.
- Ağırlıkların toplamı, bu grafikten oluşturulabilecek tüm yayılan ağaçlar arasında minimumdur.
Kruskal'ın algoritması için adım dizisi aşağıdaki gibidir:
- İlk önce tüm kenarları en düşük ağırlıktan en yükseğe doğru sıralayın.
- En düşük ağırlıkla avantaj sağlayın ve onu kapsayan ağaca ekleyin. Döngü oluşturulursa, kenarı atın.
- Tüm köşeler dikkate alınana kadar 1. adımdaki gibi kenarlar eklemeye devam edin.
Kruskal Algoritması için sözde kod
Aşağıda Kruskal’ın Algoritması için sözde kod verilmiştir
Şimdi Kruskal’ın algoritmasının resmine bakalım.
Şimdi 2-4 olan en az ağırlığa sahip kenarı seçiyoruz.
Ardından, bir sonraki en kısa kenar 2-3'ü seçin.
Sonra en kısa kenara sahip bir sonraki kenarı seçeriz ve bu bir döngü oluşturmaz, yani 0-3
youtube videolarını mp3'e dönüştürmenin en iyi yolu
Sonraki adım, bir döngü oluşturmaması için en kısa kenarı seçmektir. Bu 0-1.
Gördüğümüz gibi, tüm köşeleri kapladık ve burada minimum maliyetle yayılan bir ağaç var.
Sonra, Kruskal Algoritmasını C ++ kullanarak uygulayacağız.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i Çıktı:
Kruskal Algoritmasına Göre Minimum Genişleme Ağacı (MST):
Kenar: Ağırlık
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Yukarıdaki Kruskal algoritmasının gösteriminde kullandığımız aynı örnek grafiği programda kullandığımıza dikkat edin. Bu uygulamada iki vektörden yararlanıyoruz; biri grafiği depolamak için diğeri minimum kapsayan ağacı depolamak için. En az ağırlığa sahip kenarları özyinelemeli olarak buluruz ve tüm köşeler örtülene kadar bunları MST vektörüne ekleriz.
Prim Algoritması
Prim'in algoritması, bir grafiğin ağacını kapsayan minimum sınırı bulmak için başka bir algoritmadır. Kruskal’ın grafik kenarlarıyla başlayan algoritmasının aksine, Prim’in algoritması bir tepe noktasıyla başlar. Bir tepe noktasıyla başlıyoruz ve tüm köşeler örtülene kadar en az ağırlıklı kenarlar eklemeye devam ediyoruz.
Prim Algoritması için adım dizisi aşağıdaki gibidir:
- Başlangıç köşe noktası olarak rastgele bir köşe seçin ve minimum yayılma ağacını başlatın.
- Diğer köşelere bağlanan kenarları bulun. Minimum ağırlığa sahip kenarı bulun ve onu kapsayan ağaca ekleyin.
- Kapsayan ağaç elde edilene kadar 2. adımı tekrarlayın.
Prim Algoritması için sözde kod
Şimdi Prim'in algoritması için bir örnek görelim.
Bunun için Kruskal algoritmasının İllüstrasyonunda kullandığımız örnek grafiği kullanıyoruz.
Rastgele köşe olarak 2. düğümü seçelim.
Daha sonra 2'den en az ağırlığa sahip kenarı seçiyoruz. 2-4 kenarını seçiyoruz.
Ardından, yayılma ağacında henüz bulunmayan başka bir tepe noktası seçiyoruz. Kenar 2-3'ü seçiyoruz.
Şimdi yukarıdaki köşelerden en az ağırlığa sahip bir kenar seçelim. En az ağırlığa sahip olan 3-0 kenarımız var.
Sonra, tepe 0'dan en az ağırlığa sahip bir kenar seçiyoruz. Bu, 0-1 kenarıdır.
Yukarıdaki şekilden, şimdi grafikteki tüm köşeleri kapladığımızı ve minimum maliyetle eksiksiz bir kapsayan ağaç elde ettiğimizi görüyoruz.
Şimdi Prim'in algoritmasını C ++ 'da uygulayalım.
Bu programda da girdi olarak yukarıdaki örnek grafiği kullandığımıza dikkat edin, böylece program tarafından verilen çıktıyı resimle karşılaştırabiliriz.
Program aşağıda verilmiştir:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } Çıktı:
Prim Algoritmasına göre Minimum Kapsama Ağacı:
Kenar: Ağırlık
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Yayılan Ağaç Uygulamaları
Minimum Yayılma Ağaçlarının bazı uygulamaları aşağıdaki gibidir:
# 1) İletişim Ağı Kurulumu: İletişim bağlantılarını kullanarak bir iletişim ağı kurmak istediğimizde, iki nokta arasında iletişim bağlantıları kurmanın maliyeti en iyi MST kullanılarak belirlenir.
# 2) Küme Analizi: Minimum yayılan ağaç bularak ve en pahalı k-1 kenarlarını silerek K-kümeleme problemini çözmek için kullanılabilir.
# 3) Karayolu / Demiryolu Ağlarının Yerleştirilmesi: Şehirler arasında veya içinde çeşitli karayolu veya demiryolu ağları döşediğimizde, projenin maliyeti çok önemli bir faktördür. Minimum yayılan ağaçları kullanarak minimum maliyetle en iyi yolu bulabiliriz.
# 4) Konut Tesislerinin Planlanması: Bir dizi eve sağlanacak elektrik, su, kanalizasyon vb. Tesislerin de optimum maliyette olması gerekir ve bu bir MST kullanılarak yapılır.
# 5) Seyahat Eden Satıcı Problemini Çözme: Her noktayı en az bir kez ziyaret etmeyi gerektiren seyyar satıcı problemini çözmek için bir MST kullanabiliriz.
Sonuç
Minimum yayılma ağacı, g grafiğinin alt kümesidir ve bu alt küme, grafiğin tüm köşelerine sahiptir ve köşeleri birleştiren kenarların toplam maliyeti minimumdur.
Grafikten minimum yayılma ağacını bulmak için iki algoritma, yani Kruskal ve Prim’leri tartıştık. Kapsayan ağacın Uygulamaları da bu eğitimde burada açıklanmıştır.
=> En İyi C ++ Eğitim Öğreticilerine Buradan Göz Atın.
Önerilen Kaynaklar
- Örneklerle Java Yansıtma Eğitimi
- C ++ 'da B Ağacı ve B + Ağacı Veri Yapısı
- Örneklerle Python DateTime Eğitimi
- Bugzilla Eğitimi: Hata Yönetimi Aracı Uygulamalı Eğitimi
- C ++ 'da İkili Ağaç Veri Yapısı
- Yeni Başlayanlar İçin 20+ MongoDB Eğitimi: Ücretsiz MongoDB Kursu
- Örnek ile MongoDB Parçalama Eğitimi
- MongoDB Veritabanı Oluşturma Eğitimi
