Prim Algoritması

#Nasıl çalışır?

Prim algoritması da minimum kapsayan ağacı bulur ama Kruskal'dan farklı bir yol izler: kenarları tek tek sıralamak yerine ağacı bir başlangıç düğümünden büyütür.

Her adımda ağacın içindeki bir düğümü dışarıdaki bir düğüme bağlayan en ucuz kenar seçilir ve o düğüm ağaca katılır. Dışarıdaki her düğüm için "ağaca en ucuz bağlantı" (key) tutulur ve bir öncelik kuyruğuyla en küçüğü bulunur.

Yapısı Dijkstra'ya çok benzer; tek fark karşılaştırılan değerdir. Dijkstra başlangıca olan toplam mesafeye (dist[u] + w), Prim ise yalnızca kenarın ağırlığına (w) bakar. Başlangıç düğümü hangisi olursa olsun toplam ağırlık aynıdır.

#Kendin dene

#Adım adım

1. 01key[başlangıç] = 0, diğer tüm key değerleri ∞.
2. 02Ağacın dışındaki düğümlerden key değeri en küçük olanı (u) seç ve ağaca ekle.
3. 03u'nun dışarıdaki her komşusu v için kenar ağırlığı w < key[v] ise key[v] = w ve prev[v] = u yap.
4. 04Tüm düğümler ağaca katılana kadar tekrarla; prev[] kenarları ağacı oluşturur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

import heapq

EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
graph = {v: [] for v in range(1, 8)}
for a, b, w in EDGES:
    graph[a].append((b, w))
    graph[b].append((a, w))


def prim(start: int):
    in_tree, order, total = set(), [], 0
    heap = [(0, start)]  # (cheapest known link to the tree, node)
    while heap:
        w, u = heapq.heappop(heap)
        if u in in_tree:
            continue  # an outdated, more expensive link
        in_tree.add(u)
        order.append(u)
        total += w
        for v, weight in graph[u]:
            if v not in in_tree:
                heapq.heappush(heap, (weight, v))
    return order, total


order, total = prim(1)
print(" ".join(map(str, order)))  # the order nodes joined the tree
print(total)

#Karmaşıklık

Yoğun graflarda (E ≈ V²) heap'siz dizi sürümü O(V²) ile Kruskal'ın O(E log E) = O(V² log V) maliyetinden hızlıdır. Seyrek graflarda Kruskal genellikle daha basit ve hızlıdır. Graf bağlı değilse Prim yalnızca başlangıcın bulunduğu parçayı kapsar.

#Ne zaman kullanılır?

Yoğun graflarda MST (ör. her şehrin her şehre bağlanabildiği bir ağ), labirent üretimi (rastgele ağırlıklarla Prim güzel labirentler üretir) ve ağın bir merkezden büyüyerek kurulduğu durumlar Prim için uygundur.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.