Gerçek Dünya Problemleri ve Çözümleri
Union-Find, birçok önemli problemin temel yapı taşıdır. Bu bölümde gerçek uygulama örneklerini göreceğiz.
Minimum Spanning Tree algoritmasında döngü kontrolü.
Graf bölümünde detaylı göreceğiz!
Sıvı veya elektrik yukarıdan aşağıya geçebilir mi?
Monte Carlo simülasyonu
Arkadaşlık grupları, topluluk tespiti.
Dinamik bağlantı sorguları
Benzer pikselleri grupla, nesneleri ayır.
Bölge büyütme algoritması
İki bilgisayar aynı ağda mı?
Dinamik graf sorguları
Number of Islands, Accounts Merge, vb.
Popüler mülakat soruları
Bir grafta tüm düğümleri minimum maliyetle bağlayan ağaç.
Kruskal algoritması: Kenarları sırala, döngü oluşturmayanları ekle.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp == rq: return False
if self.rank[rp] < self.rank[rq]: rp, rq = rq, rp
self.parent[rq] = rp
if self.rank[rp] == self.rank[rq]: self.rank[rp] += 1
return True
def connected(self, p, q):
return self.find(p) == self.find(q)
def kruskal_mst(n, edges):
"""
Kruskal MST Algoritması
Args:
n: Düğüm sayısı
edges: [(weight, u, v), ...] formatında kenarlar
Returns:
MST kenarları ve toplam ağırlık
"""
# Kenarları ağırlığa göre sırala
edges = sorted(edges)
uf = UnionFind(n)
mst = []
total_weight = 0
for weight, u, v in edges:
# Döngü kontrolü: u ve v farklı kümelerde mi?
if not uf.connected(u, v):
# Kenarı MST'ye ekle
mst.append((u, v, weight))
total_weight += weight
# Kümeleri birleştir
uf.union(u, v)
print(f" Kenar ({u}-{v}, w={weight}) eklendi ✓")
else:
print(f" Kenar ({u}-{v}, w={weight}) atlandı (döngü) ✗")
return mst, total_weight
# Örnek graf
print("=" * 50)
print("KRUSKAL MST ÖRNEĞİ")
print("=" * 50)
# Kenarlar: (weight, u, v)
edges = [
(4, 0, 1), (8, 0, 7), (11, 1, 7),
(8, 1, 2), (7, 2, 3), (4, 2, 5),
(2, 2, 8), (9, 3, 4), (14, 3, 5),
(10, 4, 5), (2, 5, 6), (1, 6, 7),
(6, 6, 8), (7, 7, 8)
]
print(f"\nGraf: 9 düğüm, {len(edges)} kenar")
print("\nKruskal algoritması çalışıyor:\n")
mst, total = kruskal_mst(9, edges)
print(f"\nMST Kenarları: {mst}")
print(f"Toplam Ağırlık: {total}")
print(f"\n→ Graf bölümünde Kruskal'ı detaylı göreceğiz!")class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n # Her kümenin boyutu
self._count = n
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp == rq: return False
if self.rank[rp] < self.rank[rq]: rp, rq = rq, rp
self.parent[rq] = rp
self.size[rp] += self.size[rq]
if self.rank[rp] == self.rank[rq]: self.rank[rp] += 1
self._count -= 1
return True
def connected(self, p, q):
return self.find(p) == self.find(q)
def component_size(self, p):
return self.size[self.find(p)]
def count(self):
return self._count
class SocialNetwork:
"""Sosyal ağ analizi için Union-Find wrapper"""
def __init__(self, users):
self.users = users
self.user_to_id = {u: i for i, u in enumerate(users)}
self.id_to_user = {i: u for i, u in enumerate(users)}
self.uf = UnionFind(len(users))
self.friendships = []
def add_friendship(self, user1, user2):
"""İki kullanıcıyı arkadaş yap"""
id1, id2 = self.user_to_id[user1], self.user_to_id[user2]
if self.uf.union(id1, id2):
self.friendships.append((user1, user2))
return True
return False
def are_connected(self, user1, user2):
"""İki kullanıcı aynı toplulukta mı?"""
id1, id2 = self.user_to_id[user1], self.user_to_id[user2]
return self.uf.connected(id1, id2)
def get_communities(self):
"""Tüm toplulukları döndür"""
communities = {}
for user, uid in self.user_to_id.items():
root = self.uf.find(uid)
if root not in communities:
communities[root] = []
communities[root].append(user)
return list(communities.values())
def community_size(self, user):
"""Kullanıcının topluluğundaki kişi sayısı"""
uid = self.user_to_id[user]
return self.uf.component_size(uid)
def num_communities(self):
"""Toplam topluluk sayısı"""
return self.uf.count()
# Demo
print("=" * 60)
print("SOSYAL AĞ ANALİZİ")
print("=" * 60)
users = ["Ali", "Berk", "Cemre", "Deniz", "Elif",
"Fatma", "Gül", "Hakan", "Irmak", "Jale"]
network = SocialNetwork(users)
print(f"\n👥 Kullanıcılar: {users}")
print(f"📊 Başlangıç: {network.num_communities()} ayrı topluluk")
# Arkadaşlıklar
friendships = [
("Ali", "Berk"), # Grup 1 başlangıç
("Cemre", "Deniz"), # Grup 2 başlangıç
("Elif", "Fatma"), # Grup 3 başlangıç
("Gül", "Hakan"), # Grup 4 başlangıç
("Ali", "Cemre"), # Grup 1+2 birleşti
("Elif", "Gül"), # Grup 3+4 birleşti
("Irmak", "Ali"), # Irmak grup 1+2'ye katıldı
]
print("\n🤝 Arkadaşlıklar ekleniyor:")
for u1, u2 in friendships:
network.add_friendship(u1, u2)
print(f" {u1} ↔ {u2}")
print(f"\n📊 Şu an {network.num_communities()} topluluk var")
# Toplulukları göster
print("\n🏘️ Topluluklar:")
for i, community in enumerate(network.get_communities(), 1):
print(f" Grup {i} ({len(community)} kişi): {', '.join(community)}")
# Sorgular
print("\n🔍 Bağlantı Sorguları:")
queries = [
("Ali", "Deniz"), # Aynı grupta
("Ali", "Fatma"), # Farklı grupta
("Elif", "Hakan"), # Aynı grupta
("Jale", "Ali"), # Jale tek başına
]
for u1, u2 in queries:
connected = network.are_connected(u1, u2)
symbol = "✅" if connected else "❌"
print(f" {u1} ↔ {u2}: {symbol}")
# İstatistikler
print("\n📈 Topluluk Boyutları:")
for user in ["Ali", "Elif", "Jale"]:
size = network.community_size(user)
print(f" {user}'nin topluluğu: {size} kişi")2D grid'de kaç ada var? 1'ler kara, 0'lar su. Yatay/dikey bitişik 1'ler aynı ada.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = 0 # Ada sayısı
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp == rq: return
if self.rank[rp] < self.rank[rq]: rp, rq = rq, rp
self.parent[rq] = rp
if self.rank[rp] == self.rank[rq]: self.rank[rp] += 1
self.count -= 1 # İki ada birleşti
def add_island(self):
self.count += 1
def num_islands(grid):
"""
LeetCode 200: Number of Islands
Union-Find çözümü:
1. Her 1 hücresini bir ada olarak başlat
2. Komşu 1'leri birleştir
3. Final ada sayısını döndür
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
def cell_id(r, c):
return r * cols + c
# Grid'i tara
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
uf.add_island()
if r > 0 and grid[r-1][c] == '1':
uf.union(cell_id(r, c), cell_id(r-1, c))
if c > 0 and grid[r][c-1] == '1':
uf.union(cell_id(r, c), cell_id(r, c-1))
return uf.count
# Test
print("=" * 50)
print("NUMBER OF ISLANDS (LeetCode 200)")
print("=" * 50)
grid1 = [['1','1','1'],['1','0','0'],['0','0','1']]
print("\nGrid 1:")
for row in grid1: print(" " + " ".join(row))
print(f"Ada sayısı: {num_islands(grid1)}") # 2
grid2 = [['1','1','0','0'],['0','0','1','0'],['0','0','0','1']]
print("\nGrid 2:")
for row in grid2: print(" " + " ".join(row))
print(f"Ada sayısı: {num_islands(grid2)}") # 3Her hesap [isim, email1, email2, ...] şeklinde. Aynı email'e sahip hesapları birleştirin.
class UnionFind:
def __init__(self):
self.parent = {}
def find(self, x):
if x not in self.parent:
self.parent[x] = x
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
def accounts_merge(accounts):
uf = UnionFind()
email_to_name = {}
# Her hesaptaki email'leri birleştir
for account in accounts:
name = account[0]
first_email = account[1]
for email in account[1:]:
email_to_name[email] = name
uf.union(email, first_email)
# Root'a göre grupla
from collections import defaultdict
groups = defaultdict(list)
for email in email_to_name:
groups[uf.find(email)].append(email)
# Sonuçları formatla
result = []
for root, emails in groups.items():
name = email_to_name[root]
result.append([name] + sorted(emails))
return result
# Test
accounts = [
["Ali", "ali@gmail.com", "ali@yahoo.com"],
["Berk", "berk@gmail.com"],
["Ali", "ali@gmail.com", "ali_work@corp.com"],
["Cemre", "cemre@outlook.com"]
]
print("Hesaplar:")
for acc in accounts:
print(f" {acc}")
print("\nBirleştirilmiş:")
for acc in accounts_merge(accounts):
print(f" {acc}")N düğümlü ağaca 1 fazla kenar eklendi. Döngü oluşturan kenarı bulun.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp == rq:
return False # Zaten bağlı!
if self.rank[rp] < self.rank[rq]:
rp, rq = rq, rp
self.parent[rq] = rp
if self.rank[rp] == self.rank[rq]:
self.rank[rp] += 1
return True
def find_redundant_connection(edges):
n = len(edges)
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return [u, v] # Bu kenar döngü oluşturdu!
return []
# Test
print("=" * 50)
print("REDUNDANT CONNECTION (LeetCode 684)")
print("=" * 50)
test_cases = [
[[1,2], [1,3], [2,3]],
[[1,2], [2,3], [3,4], [1,4], [1,5]],
]
for edges in test_cases:
print(f"\nEdges: {edges}")
result = find_redundant_connection(edges)
print(f"Fazladan kenar: {result}")N×N grid var. Her hücre açık veya kapalı. Üstten alta bir yol var mı?
Uygulama: Sıvı geçirgenliği, elektrik iletkenliği, ormanda yangın yayılımı.
import random
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp == rq: return
if self.rank[rp] < self.rank[rq]: rp, rq = rq, rp
self.parent[rq] = rp
if self.rank[rp] == self.rank[rq]: self.rank[rp] += 1
def connected(self, p, q):
return self.find(p) == self.find(q)
class Percolation:
"""
Percolation sistemi.
N×N grid + 2 sanal düğüm (üst ve alt).
Üst düğüm: tüm üst satıra bağlı
Alt düğüm: tüm alt satıra bağlı
Percolates = üst ve alt düğüm bağlı mı?
"""
def __init__(self, n):
self.n = n
self.grid = [[False] * n for _ in range(n)]
self.open_count = 0
# N*N hücre + 2 sanal düğüm
# 0 ~ N*N-1: gerçek hücreler
# N*N: üst sanal düğüm
# N*N+1: alt sanal düğüm
self.uf = UnionFind(n * n + 2)
self.top_virtual = n * n
self.bottom_virtual = n * n + 1
def _cell_id(self, row, col):
return row * self.n + col
def open(self, row, col):
"""Hücreyi aç"""
if self.grid[row][col]:
return # Zaten açık
self.grid[row][col] = True
self.open_count += 1
cell = self._cell_id(row, col)
# Üst satırsa, üst sanal düğüme bağla
if row == 0:
self.uf.union(cell, self.top_virtual)
# Alt satırsa, alt sanal düğüme bağla
if row == self.n - 1:
self.uf.union(cell, self.bottom_virtual)
# Komşularla birleştir
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < self.n and 0 <= nc < self.n and self.grid[nr][nc]:
self.uf.union(cell, self._cell_id(nr, nc))
def is_open(self, row, col):
return self.grid[row][col]
def percolates(self):
"""Sistem percolate ediyor mu?"""
return self.uf.connected(self.top_virtual, self.bottom_virtual)
def display(self):
"""Grid'i göster"""
symbols = {False: '█', True: '░'}
for row in self.grid:
print(" " + "".join(symbols[c] for c in row))
def percolation_threshold(n, trials=100):
"""
Monte Carlo simülasyonu ile percolation eşiğini tahmin et.
Eşik: Sistemin percolate etmesi için gereken minimum açık hücre oranı.
Teorik değer ≈ 0.593 (N→∞ için)
"""
thresholds = []
for _ in range(trials):
perc = Percolation(n)
cells = [(r, c) for r in range(n) for c in range(n)]
random.shuffle(cells)
for row, col in cells:
perc.open(row, col)
if perc.percolates():
threshold = perc.open_count / (n * n)
thresholds.append(threshold)
break
return sum(thresholds) / len(thresholds)
# Demo
print("=" * 50)
print("PERCOLATION SİMÜLASYONU")
print("=" * 50)
# Küçük örnek
print("\nKüçük örnek (5×5):")
perc = Percolation(5)
# Bazı hücreleri aç
opens = [(0,1), (1,1), (2,1), (2,2), (3,2), (4,2)]
for r, c in opens:
perc.open(r, c)
print(f"\nopen({r}, {c}):")
perc.display()
print(f" Percolates: {perc.percolates()}")
# Monte Carlo simülasyonu
print("\n" + "─" * 50)
print("Monte Carlo Simülasyonu")
print("─" * 50)
random.seed(42)
for n in [10, 20]:
threshold = percolation_threshold(n, trials=50)
print(f"N={n}: Percolation eşiği ≈ {threshold:.3f}")
print("\nTeorik eşik (N→∞): ≈ 0.593")Sonraki Bölüm: Graf algoritmaları! Union-Find'ı Kruskal MST'de kullanacağız.