Kruskal ve Prim Algoritmaları
Temel kavram
Kenar tabanlı
Düğüm tabanlı
Veri yapısı
Minimum Spanning Tree (MST), bir ağırlıklı grafın tüm düğümlerini birbirine bağlayan, toplam kenar ağırlığı en düşük olan ağaç yapısıdır.
Bir şehirde tüm evleri elektrik şebekesine bağlamak istiyorsunuz. Her sokağa kablo döşemenin bir maliyeti var. Tüm evlerin elektrik alması için minimum kablo maliyeti ne olmalı?
Bu tam olarak MST problemidir: Evler = düğümler, sokaklar = kenarlar, kablo maliyeti = ağırlık.
Şehirleri/evleri minimum kablo maliyetiyle birbirine bağlama. Türkiye'nin elektrik dağıtım ağı planlaması.
Fiber optik kablo döşeme, baz istasyonu ağı kurma. Minimum altyapı maliyetiyle maksimum kapsama.
Köyleri/şehirleri birbirine bağlayan en ekonomik yol ağı. Türkiye hızlı tren ağı planlaması.
Bölgelere minimum boru hattı maliyetiyle su/gaz dağıtımı.
LAN/WAN tasarımı. Router'ları minimum kablo ile bağlama, spanning tree protocol.
Single-linkage hierarchical clustering. MST kenarlarını keserek kümeler oluşturma.
Kruskal ve Prim algoritmalarının adım adım çalışmasını izleyin
Kenar odaklı, greedy (açgözlü) yaklaşım:
İki düğüm zaten aynı bileşendeyse (bağlıysa), aralarına kenar eklersek döngü oluşur!
Çözüm: Union-Find (Disjoint Set Union) veri yapısı
Union-Find, kümeleri verimli şekilde yönetmek için kullanılır:
x'in hangi kümeye ait olduğunu bul
Path Compression: Yol boyunca tüm düğümleri köke bağla → O(α(n)) ≈ O(1)
x ve y'nin kümelerini birleştir
Union by Rank: Küçük ağacı büyüğe bağla → dengeli ağaç
class UnionFind:
"""
Disjoint Set Union (DSU) / Union-Find
Path Compression + Union by Rank optimizasyonları ile
neredeyse O(1) amortized karmaşıklık sağlar.
"""
def __init__(self, n):
# Her düğüm başlangıçta kendi kümesinin kökü
self.parent = list(range(n))
# Rank: ağaç yüksekliği (yaklaşık)
self.rank = [0] * n
# Küme sayısı
self.num_sets = n
def find(self, x):
"""
x'in kök düğümünü bul
Path Compression: Yol üzerindeki tüm düğümleri köke bağla
"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Recursive + memoization
return self.parent[x]
def union(self, x, y):
"""
x ve y'nin kümelerini birleştir
Union by Rank: Küçük ağacı büyüğe bağla
Returns: True eğer birleştirme yapıldıysa (farklı kümelerdeydiler)
"""
root_x = self.find(x)
root_y = self.find(y)
# Zaten aynı kümedeler
if root_x == root_y:
return False
# Rank'e göre birleştir
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.num_sets -= 1
return True
def connected(self, x, y):
"""x ve y aynı kümede mi?"""
return self.find(x) == self.find(y)
# Demo
print("=== UNION-FIND DEMO ===\n")
uf = UnionFind(6)
print(f"Başlangıç: 6 ayrı küme (her düğüm kendi kümesinde)")
print(f"Küme sayısı: {uf.num_sets}\n")
operations = [
(0, 1, "0 ve 1'i birleştir"),
(2, 3, "2 ve 3'ü birleştir"),
(0, 2, "0 ve 2'yi birleştir (artık 0,1,2,3 aynı kümede)"),
(4, 5, "4 ve 5'i birleştir"),
]
for x, y, desc in operations:
result = uf.union(x, y)
print(f"union({x}, {y}): {desc}")
print(f" → Birleştirildi: {result}, Küme sayısı: {uf.num_sets}")
print(f"\n0 ve 3 bağlı mı? {uf.connected(0, 3)}") # True
print(f"0 ve 5 bağlı mı? {uf.connected(0, 5)}") # Falseclass UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal_mst(n, edges):
"""
Kruskal algoritması ile Minimum Spanning Tree bul
Args:
n: Düğüm sayısı (0'dan n-1'e)
edges: [(u, v, weight), ...] kenar listesi
Returns:
(mst_edges, total_weight) tuple
Karmaşıklık: O(E log E) - sıralama dominant
"""
# 1. Kenarları ağırlığa göre sırala
sorted_edges = sorted(edges, key=lambda e: e[2])
uf = UnionFind(n)
mst = []
total_weight = 0
print("Kenarlar (ağırlığa göre sıralı):")
for u, v, w in sorted_edges:
print(f" ({u}-{v}, w={w})")
print()
# 2. Her kenarı incele
for u, v, weight in sorted_edges:
# 3. Döngü kontrolü
if uf.union(u, v):
# Farklı bileşenlerdeydi, birleştir
mst.append((u, v, weight))
total_weight += weight
print(f"✅ Kenar ({u}-{v}, w={weight}) eklendi")
# 4. N-1 kenar bulunca dur
if len(mst) == n - 1:
break
else:
print(f"❌ Kenar ({u}-{v}, w={weight}) DÖNGÜ OLUŞTURUR, atlandı")
return mst, total_weight
# Örnek: 6 şehir arasında kablo döşeme
print("=== KRUSKAL ALGORİTMASI ===")
print("Şehirler: A=0, B=1, C=2, D=3, E=4, F=5\n")
edges = [
(0, 1, 4), # A-B
(0, 5, 2), # A-F
(1, 2, 6), # B-C
(1, 5, 5), # B-F
(2, 3, 3), # C-D
(2, 4, 5), # C-E
(3, 4, 2), # D-E
(4, 5, 4), # E-F
]
mst, total = kruskal_mst(6, edges)
print(f"\n🌲 MST Kenarları:")
for u, v, w in mst:
print(f" {u} — {v} (ağırlık: {w})")
print(f"\n📏 Toplam Maliyet: {total}")Düğüm odaklı, greedy yaklaşım (Dijkstra'ya benzer):
Her ikisi de priority queue kullanır, ama:
import heapq
from collections import defaultdict
def prim_mst(n, edges, start=0):
"""
Prim algoritması ile Minimum Spanning Tree bul
Args:
n: Düğüm sayısı
edges: [(u, v, weight), ...] kenar listesi
start: Başlangıç düğümü
Returns:
(mst_edges, total_weight) tuple
Karmaşıklık: O(E log V) - priority queue ile
"""
# Adjacency list oluştur
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
visited = set()
mst = []
total_weight = 0
# Min heap: (weight, from_node, to_node)
# Başlangıç düğümü için -1 kullanıyoruz (ilk düğüm)
pq = [(0, -1, start)]
print(f"Başlangıç düğümü: {start}\n")
while pq and len(visited) < n:
weight, from_node, to_node = heapq.heappop(pq)
# Zaten ziyaret edilmişse atla
if to_node in visited:
continue
visited.add(to_node)
if from_node != -1:
mst.append((from_node, to_node, weight))
total_weight += weight
print(f"✅ Düğüm {to_node} eklendi (kenar: {from_node}-{to_node}, w={weight})")
else:
print(f"🚀 Başlangıç düğümü {to_node} eklendi")
# Yeni düğümün komşularını heap'e ekle
for neighbor, edge_weight in graph[to_node]:
if neighbor not in visited:
heapq.heappush(pq, (edge_weight, to_node, neighbor))
return mst, total_weight
# Aynı örnek
print("=== PRİM ALGORİTMASI ===")
print("Şehirler: A=0, B=1, C=2, D=3, E=4, F=5\n")
edges = [
(0, 1, 4), # A-B
(0, 5, 2), # A-F
(1, 2, 6), # B-C
(1, 5, 5), # B-F
(2, 3, 3), # C-D
(2, 4, 5), # C-E
(3, 4, 2), # D-E
(4, 5, 4), # E-F
]
mst, total = prim_mst(6, edges, start=0)
print(f"\n🌲 MST Kenarları:")
for u, v, w in mst:
print(f" {u} — {v} (ağırlık: {w})")
print(f"\n📏 Toplam Maliyet: {total}")| Özellik | Kruskal | Prim |
|---|---|---|
| Yaklaşım | Kenar odaklı (global) | Düğüm odaklı (local/incremental) |
| Veri Yapısı | Union-Find | Priority Queue (Min Heap) |
| Zaman Karmaşıklığı | O(E log E) | O(E log V) |
| Seyrek Graf (E ≈ V) | ✅ Daha İyi | 🔶 İyi |
| Yoğun Graf (E ≈ V²) | 🔶 Orta | ✅ Daha İyi |
| Paralel İşleme | ✅ Kolay | ❌ Zor |
| Dinamik Güncelleme | 🔶 Orta | ✅ Daha Kolay |
Bir grafın herhangi bir kesiti için, kesiti geçen minimum ağırlıklı kenar mutlaka MST'dedir.
Bir döngüdeki maksimum ağırlıklı kenar, hiçbir MST'de bulunamaz.
Tüm kenar ağırlıkları farklıysa, MST tektir. Aynı ağırlıklar varsa birden fazla MST olabilir.
| Algoritma | Zaman | Alan | Not |
|---|---|---|---|
| Kruskal | O(E log E) | O(V) | Union-Find gerektirir |
| Prim (Binary Heap) | O(E log V) | O(V) | Dijkstra'ya benzer |
| Prim (Fibonacci Heap) | O(E + V log V) | O(V) | Teorik olarak en hızlı |