Algoritmalar
Edmonds-Karp
BFS tabanlı Edmonds-Karp algoritmasını öğrenirsin.
Edmonds-Karp
Edmonds-Karp, Ford-Fulkerson yönteminin BFS kullanan özel halidir. Artık yol her zaman en kısa (en az kenarlı) olacak şekilde seçilir.
BFS kullanımı, algoritmanın O(V·E²) gibi garantili bir polinomsal karmaşıklığa sahip olmasını sağlar. Ford-Fulkerson'ın aksine yol seçimi deterministiktir.
Bu sağlamlık, Edmonds-Karp'ı pratikte tercih edilen bir yöntem yapar.
BFS ile yol bulma
Edmonds-Karp, artık yolu BFS ile bulur. Kaynaktan başlayarak her düğümün ebeveynini kaydederiz; hedefe ulaştığımızda ebeveyn zinciri yolu verir.
BFS sırasında yalnızca kalan kapasitesi sıfırdan büyük kenarları izleriz. Bu, artık grafta geçerli bir yol bulmayı sağlar.
Bulunan yolda darboğaz, kenar kapasitelerinin minimimidir; akış bu değer kadar artırılır.
Uygulama edmonds_karp fonksiyonu
edmonds_karp(capacity, source, sink) yaz. BFS ile maksimum akışı döndür. print(edmonds_karp([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't')) ile 5 yazdır.
Örnek çözümü göster
def edmonds_karp(capacity, source, sink):
# BFS tabanlı maksimum akış
from collections import deque, defaultdict
graph = defaultdict(dict)
for u, v, c in capacity:
graph[u][v] = graph[u].get(v, 0) + c
graph[v][u] = graph[v].get(u, 0)
max_flow = 0
while True:
parent = {source: None}
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in parent and graph[u][v] > 0:
parent[v] = u
queue.append(v)
if sink not in parent:
break
flow = float('inf')
v = sink
while v != source:
u = parent[v]
flow = min(flow, graph[u][v])
v = u
v = sink
while v != source:
u = parent[v]
graph[u][v] -= flow
graph[v][u] = graph[v].get(u, 0) + flow
v = u
max_flow += flow
return max_flow
print(edmonds_karp([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't'))
Kendini test et
-
Edmonds-Karp kavramları
- BFS
- En kısa yol
- O(V·E²)
- Karmaşıklık
- kuyruk
- deque
- deterministik
- Yol seçimi
-
Edmonds-Karp'ın karmaşıklığı nedir?
from collections import deque
Cevabı göster
O(V·E²) — Edmonds-Karp O(V·E²) zaman alır.
-
BFS kuyruk
queue = deque([____])
Cevabı göster
queue = deque([source])
Sıradaki ders: Maksimum akış minimum kesme
