Edmonds-Karp
- Algoritmalar kursu
- Uzman seviye
- Ders 27/41
- 4 dk
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.
Başlangıç kodu
def edmonds_karp(capacity, source, sink):
# BFS tabanlı maksimum akışÖrnek çözüm
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'))Beklenen çıktı
5
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Edmonds-Karp kavramları
| Kavram | Anlamı |
|---|---|
BFS |
En kısa yol |
O(V·E²) |
Karmaşıklık |
kuyruk |
deque |
deterministik |
Yol seçimi |
2 Edmonds-Karp'ın karmaşıklığı nedir?
from collections import deque- O(2ⁿ)
- O(V²)
- O(E³)
- O(V·E²) Doğru cevap
Açıklama: Edmonds-Karp O(V·E²) zaman alır.
3 BFS kuyruk
queue = deque([____])queue = deque([source])Açıklama: BFS kaynaktan başlar.