37
правок
Изменения
Нет описания правки
=== Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину ===
При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.
Дана сеть (рис. 1).[[Файл:F-f.1.png|thumb|center|рис. 1]]Благодаря двум итерациям (рис. 2 и рис. 3)[[Файл:F-f.2.png|thumb|center|рис. 2]][[Файл:F-f.3.png|thumb|center|рис. 3]]рёбра <tex>AB, AC, BD, CD</tex> насытились лишь на 1.Конечная сеть будет получена ещё через 1998 итераций (рис. 4).[[Файл:F-f.4.png|thumb|center|рис. 4]]
== См. также ==
* [[Теорема Форда-Фалкерсона]]
== Литература ==
Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]
