Bu yazımızda Kruskal'ın algoritmasını tartışacağız. Burada ayrıca Kruskal algoritmasının karmaşıklığını, çalışmasını, örneğini ve uygulamasını da göreceğiz.
Ancak doğrudan algoritmaya geçmeden önce yayılan ağaç ve minimum yayılan ağaç gibi temel terimleri anlamalıyız.
Yayılan ağaç - Yayılan ağaç, yönlendirilmemiş bağlantılı bir grafiğin alt grafiğidir.
Az yer kaplayan ağaç - Minimum yayılan ağaç, kenar ağırlıklarının toplamının minimum olduğu kapsayan ağaç olarak tanımlanabilir. Yayılan ağacın ağırlığı, yayılan ağacın kenarlarına verilen ağırlıkların toplamıdır.
Şimdi ana konumuzla başlayalım.
Kruskal Algoritması bağlantılı ağırlıklı grafik için minimum kapsayan ağacı bulmak için kullanılır. Algoritmanın ana hedefi, grafiğin her köşesini geçebileceğimiz kenarların alt kümesini bulmaktır. Global optimuma odaklanmak yerine, her aşamada optimum çözümü bulan açgözlü yaklaşımı izler.
Kruskal'ın algoritması nasıl çalışıyor?
Kruskal'ın algoritmasında en düşük ağırlığa sahip kenarlardan başlayıp hedefe ulaşana kadar kenarları eklemeye devam ediyoruz. Kruskal algoritmasını uygulama adımları şu şekilde sıralanmıştır:
- Öncelikle tüm kenarları düşük ağırlıktan yükseğe doğru sıralayın.
- Şimdi en düşük ağırlığa sahip kenarı alın ve yayılan ağaca ekleyin. Eklenecek kenar bir döngü oluşturuyorsa kenarı reddedin.
- Tüm köşelere ulaşana ve minimum yayılan ağaç oluşturulana kadar kenarları eklemeye devam edin.
Kruskal algoritmasının uygulamaları:
- Kruskal'ın algoritması şehirler arasındaki elektrik kablolarını düzenlemek için kullanılabilir.
- LAN bağlantılarını düzenlemek için kullanılabilir.
Kruskal algoritmasının örneği
Şimdi bir örnek kullanarak Kruskal algoritmasının işleyişini görelim. Bir örnek kullanarak Kruskal'ın algoritmasını anlamak daha kolay olacaktır.
Ağırlıklı bir grafiğin -
Yukarıdaki grafiğin kenarlarının ağırlığı aşağıdaki tabloda verilmiştir -
| Kenar | AB | AC | reklam | ANCAK | M.Ö | CD | İLE İLGİLİ |
| Ağırlık | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Şimdi yukarıda verilen kenarları ağırlıklarına göre artan şekilde sıralayın.
| Kenar | AB | İLE İLGİLİ | M.Ö | CD | ANCAK | AC | reklam |
| Ağırlık | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Şimdi minimum kapsayan ağacı oluşturmaya başlayalım.
javascript uyarı kutusu
Aşama 1 - İlk önce kenarı ekleyin AB ağırlıkla 1 MST'ye.
Adım 2 - Kenar ekleyin İLE İLGİLİ ağırlıkla 2 Döngüyü yaratmadığı için MST'ye.
Aşama 3 - Kenar ekleyin M.Ö ağırlıkla 3 Herhangi bir döngü veya döngü oluşturmadığı için MST'ye.
Adım 4 - Şimdi, kenarı seç CD ağırlıkla 4 Döngüyü oluşturmadığı için MST'ye.
Adım 5 - Bundan sonra kenarı seçin ANCAK ağırlıkla 5. Bu kenarın dahil edilmesi döngüyü yaratacaktır, o yüzden onu atın.
Adım 6 - Kenarı seç AC ağırlıkla 7. Bu kenarın dahil edilmesi döngüyü yaratacaktır, o yüzden onu atın.
Adım 7 - Kenarı seç reklam ağırlıkla 10. Bu kenarın dahil edilmesi aynı zamanda döngüyü de oluşturacaktır, o yüzden onu atın.
Dolayısıyla verilen ağırlıklı grafikten Kruskal algoritması kullanılarak elde edilen son minimum kapsayan ağaç şu şekildedir:
MST'nin maliyeti = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10'dur.
Şimdi yukarıdaki ağaçta kenar sayısı köşe sayısı eksi 1'e eşit oluyor. Yani algoritma burada duruyor.
Algoritma
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Kruskal algoritmasının karmaşıklığı
Şimdi Kruskal algoritmasının zaman karmaşıklığını görelim.
Kruskal algoritmasının zaman karmaşıklığı O(E logE) veya O(V logV) olup, burada E hayırdır. kenarları ve V hayırdır. köşelerden oluşan.
Kruskal algoritmasının uygulanması
Şimdi Kruskal algoritmasının uygulamasını görelim.
Programı: Kruskal algoritmasını C++ dilinde uygulayan bir program yazın.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>