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

 Kruskal algoritması ~ Gerçek hayat örneği ve C++ Kodu
Okunuyor 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.

Cannaregio Ponte Scalzi Santa Corce Dell ‘Orto Ferrovia Piazzale Roma San Polo Dorso Duro San Marco St. Mark Basilica Castello Arsenale
A B C D E F G H I J K L

 

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ı –
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
    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, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])
{
    int x, y;
    long long cost, minimumCost = 0;
    for(int i = 0;i < edges;++i)
    {
        // Kenarları artan düzende baştan seçerek tek tek seçme
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        // Seçilen kenarın bir döngü oluşturup oluşturmadığını kontrol edin
        if(root(x) != root(y))
        {
            minimumCost += cost;
            union1(x, y);
        }    
    }
    return minimumCost;
}

int main()
{
    int x, y;
    long long weight, cost, minimumCost;
    initialize();
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        p[i] = make_pair(weight, make_pair(x, y));
    }
    //Kenarları artan düzende sıralayın
    sort(p, p + edges);
    minimumCost = kruskal(p);
    cout << minimumCost << endl;
    return 0;
}
 Daha fazla örnek için ramazanakbuz.com sitemizdeki diğer algoritmalarıda inceleyebilirsiniz.

 

Yapılan Yorumlar

Bir Cevap Yazın

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