Algorithmen und Datenstrukturen · Senior · Frage 52 von 75
Welcher Algorithmus findet den maximalen Fluss in einem Netzwerk?
- 1Edmonds-Karp (Ford-Fulkerson mit BFS)
- 2Floyds Zyklusprüfung „Hase und Igel“
- 3Kruskals minimaler Spannbaum
Antwort zeigen
Richtige Antwort: Edmonds-Karp (Ford-Fulkerson mit BFS)
Erklärung
Er findet wiederholt per BFS einen kürzesten augmentierenden Pfad und schiebt Fluss entlang, in O(V × E²). Maximaler Fluss löst auch bipartites Matching, etwa Aufgaben an Mitarbeiter zu verteilen.