Kruskal MST

Graflar O(E log E) O(V)

Kenarları ağırlık sırasına göre ekleyerek minimum kapsayan ağaç kurar; döngü kenarlarını birleştir-bul ile reddeder.

1/19

Her düğüm kendi kümesine konuyor (rozet = küme kökü).

DeğişmezTutulan kenarlar bir orman oluşturur; her biri iki farklı bileşeni birleştiren en hafif kenardı.

mevcutsınırziyaret edildiağaç kenarı

kruskal.c

#define V 6
 
int parent[V];
int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}
 
void kruskal(Edge edges[], int m) {
    for (int i = 0; i < V; i++) parent[i] = i;
    sortByWeight(edges, m);
 
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].u), b = find(edges[i].v);
        if (a == b)
            continue;           /* same set -> cycle, skip */
        parent[a] = b;          /* union: keep this edge */
    }
}

Kruskal MST nasıl çalışır?

Tüm kenarları ağırlığa göre sırala ve en ucuzdan başlayarak al; uçları zaten bağlı olan kenarları atla (bunu union-find saptar). Bağımsız ormanlar tek MST'de birleşir.

Ne zaman kullanılır?

Seyrek graflar / düz kenar listelerinde MST; en büyük kenarları keserek kümeleme.