Prim MST

Graflar O(V²) O(V)

Bir başlangıç düğümünden minimum kapsayan ağacı büyütür; her zaman yeni bir düğüme ulaşan en ucuz kenarı ekler.

Başlangıç düğümü

1/23

0 düğümünden başlanıyor: key[0] = 0, diğerleri ∞.

DeğişmezSeçilen kenarlar tek bir ağaç oluşturur ve her biri o ağaçtan çıkan en ucuz kenardı — kesim özelliği bunu güvenli kılar.

mevcutsınırziyaret edildiağaç kenarı

prim.c

#define V 6
#define INF 1000000
 
void prim(int graph[V][V], int start) {
    int inMST[V] = {0};
    int key[V], parent[V];
    for (int i = 0; i < V; i++) key[i] = INF;
    key[start] = 0;
 
    for (int count = 0; count < V; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!inMST[v] && (u == -1 || key[v] < key[u]))
                u = v;
        inMST[u] = 1;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && !inMST[v] &&
                graph[u][v] < key[v]) {
                key[v] = graph[u][v];
                parent[v] = u;
            }
    }
}

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

Tek bir ağacı başlangıç düğümünden büyüt: her adımda ağacı yeni bir düğüme bağlayan en ucuz kenarı ekle. Kesiti geçen en ucuz kenar her zaman güvenlidir.

En kötü durum

Buradaki dizi taramasıyla O(V²); yığınla O(E log V).

Ne zaman kullanılır?

Yoğun graflarda minimum kapsayan ağaç veya ağacın belirli bir düğümden büyümesi istendiğinde.