AlgoritmaYapay ZekaYazılım

Kruskal algoritması ~ Gerçek hayat örneği ve C++ Kodu

Kablo ağı şirketlerinin çoğu, bir kentte veya şehirler grubunda kablo döşeme için en kısa yolu bulmak için Kruskal  algoritması ‘ nda Ayrık Set Birliği veri yapısını kullanmaktadır.

Bu, ayrık setlerin birliği ve minimum kapsayan ağacın örnekleri ile birlikte bu yazıya yönlendirir.

Kruskal algoritması örneğine geçmeden önce, ayrık kümelerin ne olduğunu anlayalım.

Ayrık Kümeler Nedir?

Diyelim ki 6 eleman A, B, C, D, E ve F vardır. B, C ve D bağlıdır ve E ve F birbirine eşlenmiştir. Bu, (A), (B, C, D) ve (E, F) öğelerine sahip 3 alt küme verir.

Ayrık setler, hangi öğelerin birbirine bağlı olduğunu hızlı bir şekilde belirlememize ve kapatmamıza ve iki bileşeni tek bir varlıkta birleştirebilmemize yardımcı olur.

Aykırı ayarlanmış veri yapısı iki önemli işlevden oluşur:

Find() – Belirli bir öğenin hangi alt kümeye ait olduğunu belirlemenize yardımcı olur.

Ayrıca öğenin birden fazla alt kümede olup olmadığını belirlemeye yardımcı olur.

Union() – Bir grafik döngüsel olup olmadığını kontrol etmeye yardımcı olur. Ve iki alt gruba bağlanmaya ya da bu alt kümelere katılmaya yardımcı olur.

Ayrık Kümenin Uygulanması

Önceki örnek için, set (B, C, D) için B’nin bir üst düğüm olduğunu varsayarız. Ayrık set için her düğüm için tek bir temsilci tutuyoruz.

krushal

Belirli bir düğümdeki herhangi bir öğeyi ararsak, o düğümün ana sayfasına yönlendiririz.

Bu nedenle, D’yi aradığınızda, cevap B olur.

Benzer şekilde, (A) alt kümesini (E, F) bağlayabiliriz; bu, düğüm A’yı ana düğüm olarak verecektir.

Şimdi iki altkümemiz var, ancak hem B hem de A’nın üst düğümleri yok. Her ağaç, bağımsız bir ayrık kümedir; yani, aynı ağaçta iki veya daha fazla öğe bulunuyorsa, bunlar aynı ayrık kümenin parçasıysa, bağımsızdırlar.

Dolayısıyla, belirli bir ağaç için B temsilci ise, o zaman Ana [i] = B. B temsilci değilse, ağacın üstünü veya temsilcisini bulmak için ağacı yukarı çıkarabiliriz.

Kruskal algoritması nedir?

Kaplama ağacı, bir ağacın tüm kenarlarının ağırlıklarının toplamıdır. Bir asgari kapsayan ağaç (MST), tüm kapsayan ağaçlar arasında en düşük maliyetli olanıdır.

İşte minimum kapsayan ağaç örneği.

Kruskal Algoritması ve Prim’in minimum kapsayan ağaç algoritması, asgari kapsayan ağaçları bulmak için kullanılan iki popüler algoritma.

Kruskal algoritması , minimum kapsayan bir ağacı bulmak için aç gözlü yaklaşımı kullanır. Kruskal algoritması , her düğüm bağımsız bir ağaç olarak ele alınır ve yalnızca diğer tüm seçeneklere kıyasla en düşük maliyeti varsa, bir düğmeyi birbirine bağlar.

Kruskal algoritması ‘na adım atın:

Grafik kenarlarını ağırlıklarına göre sıralayın.
En aza indirgeme ağacına en küçük ağırlığa sahip kenardan en büyük ağırlığın kenarına kadar kenarlar eklemeye başlayın.
Yalnızca bağlantı kesilen bileşenleri bağlayan bir döngü kenarı oluşturmayan kenarlar ekleyin.
Ya da daha basit bir açıklama olarak,

Adım 1 – Tüm döngüler ve paralel kenarları kaldırın

Adım 2 – Tüm kenarları maliyetin artan sırasına göre düzenleyin

Adım 3 – En az ağırlıklı kenarlıklar ekleyin

Ancak iki köşenin bağlı olup olmadığını nasıl kontrol edersiniz? Ayrılık Kümelerinin gerçek hayat örneği burada geçerlidir.

Kruskal algoritması örneği ayrıntılı olarak

Eminim çok azınız bir kablo ağı şirketi için çalışıyor olacak, bu nedenle Kruskal algoritması sorununu daha fazla ilişkili hale getirelim.

Venedik’e yaptığınız gezi sırasında tüm önemli dünya mirası yerlerini ziyaret etmeyi planlıyorsunuz, ancak zamanında vaktiniz azalıyor. Güzergahınızı çalışmak için, ayrık kümeler kullanarak Kruskal algoritması ‘nı kullanmaya karar verdiniz.

İşte Venedik haritası.

Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Bunu, aşağıdaki gibi bir grafiğe dönüştürerek ve önemli yerleri mektuplarla ve metre cinsinden (x 100) harita üzerinde basitleştirerek basitleştirelim.

CannaregioPonte ScalziSanta CorceDell ‘OrtoFerroviaPiazzale RomaSan PoloDorso DuroSan MarcoSt. Mark BasilicaCastelloArsenale
ABCDEFGHIJKL

 

Yukarıdaki haritayı kullanarak gerçek dünyadaki örnekte Kruskal algoritması ‘nın nasıl kullanıldığını anlayın.

Adım 1- Tüm döngüler ve paralel kenarları kaldırın

Dolayısıyla verilen harita için Madonna dell’Orto (D) ile St. Mark Bazilikası (J) arasında 2.4kms (2400mts) uzunluğunda bir paralel kenar bulunur. Paralel yol kaldırılacak ve gösterim için 1.8 km (1800m) uzunluğunu koruyacağız.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

2. Adım – Grafiğin tüm kenarlarını artan düzende düzenleyin. Kruskal algoritması , her bir grubu bir ağaç olarak kabul eder ve kaç tanesinin diğer ağaçların bir parçası olduğunu kontrol etmek için ayrık kümeler uygular.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Adım 3 – En az ağırlığı olan kenarları ekleyin; En az ağırlık / maliyet ile kenarlarla başlıyoruz. Bu nedenle, B, C, sadece kenar maliyetleri sadece 1 göz önüne alınarak bağlanır.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Ben, J’nin maliyeti 1; Bir sonraki bağlantı kenarıdır.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Daha sonra, ağırlıkları = 2 olan kenarları birbirine bağlarız.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Benzer şekilde, Ağırlık = 3 olan bir kenarı olan K, L düğümünü bağlarız.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Yukarıdaki tabloda belirtildiği gibi, tüm kenarlar artan düzende bağlanır ve 2 köşe arasında hiçbir döngü veya döngü oluşturulmaz.

Bu, verilen sorunun minimum kapsama ağacı olan aşağıdaki grafiği verir.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union

Burada Kruskal’ın C ++ kullanan algoritması –
 Daha fazla örnek için ramazanakbuz.com sitemizdeki diğer algoritmalarıda inceleyebilirsiniz.

 

Etiketler

Ramazan Şerif

Selamun Aleyküm Adım Ramazan Şerif Akbuz. Bilişime olan merakım ortaokul yıllarımda başladı.7.Sınıfta Türkiye Eğitim Gönülleri Vakfı aracılığı ile girdiğim Legorobot yarışmasında Türkiye de ilk 20 ye girdik.Bilişime olan heyecanım lise yıllarımda da devam etti.Liseyi Veritabanı Programcılığı bölümünde okudum.Matematiğim zayıftı bende 2 yıllık Omü bilgisayar programcılığına geçiş yaptım.Okulu başarıyla bitirdim.2 Yıldır bir yandan Freelance olarak çalışıyor , bir yandanda iş arıyorum.Bakdım olacağı yok birazda kendimi geliştirme kararı aldım.DGS ile Fırat Üniversitesi Yazılım Mühendisliğine geldim.Maceranın devamında bir baltaya sap olabilmek dileğiyle "Zaman zam anıdır Gülüşüme sende gül üşüme"

İlgili Makaleler

Bir Cevap Yazın

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Başa dön tuşu
Kapalı
%d blogcu bunu beğendi: