Алгоритм проталкивания предпотока: как найти максимальный поток в сети (для начинающих)

Привет, будущие инженеры и программисты! Сегодня мы разберём ещё один крутой алгоритм для поиска максимального потока — алгоритм проталкивания предпотока (Push‑Relabel). Если алгоритм Форда‑Фалкерсона — это как если бы вы искали дорогу в городе с фонариком, а алгоритм Диница — как если бы вы строили уровни и шли по ним этажами, то проталкивание предпотока — это как если бы вы взяли гидравлический домкрат и начали «выдавливать» воду из источника!

Представьте, что у вас есть система водопроводных труб, и вы хотите прокачать максимальное количество воды из водонапорной башни в городской район. Но вместо того чтобы искать пути и аккуратно направлять воду, вы решили действовать по‑другому: накачать воду под давлением в башню и позволить ей «выдавливаться» через трубы, постепенно находя оптимальные пути. Это и есть идея алгоритма проталкивания предпотока!

Такой подход используется в:

Гидравлике: моделирование потоков жидкости под давлением
Сетевых технологиях: распределение трафика с учётом «приоритетов» узлов
Логистике: оптимизация грузоперевозок с промежуточными складами
Компьютерном зрении: сегментация изображений методом минимального разреза

Алгоритм был разработан Эндрю Гольдбергом и Робертом Тарьяном в 1986 году как альтернатива классическим методам поиска пути.

1. Основные понятия: «Высота» и «избыточный поток»

Чтобы понять алгоритм, давайте сначала разберёмся с новыми терминами:

Предпоток (Preflow): В отличие от обычного потока, предпоток может нарушать закон сохранения в промежуточных вершинах. То есть в некоторые вершины может «втекать» больше воды, чем «вытекать». Эта «лишняя» вода называется избыточным потоком.

Избыточный поток (Excess): Это количество «лишней» воды, которая скопилась в вершине. Если в вершину втекает 10 единиц, а вытекает 7, то избыточный поток равен 3.

Высота (Height/Label): Каждой вершине присваивается «высота» — целое число, которое показывает, насколько она «высоко» относительно стока. Исток имеет максимальную высоту (обычно равную количеству вершин), сток — высоту 0. Вода может «стекать» только с более высокой вершины на более низкую или равную по высоте.

Допустимое ребро: Ребро из вершины u в вершину v называется допустимым, если:

• У него есть остаточная пропускная способность (можно протолкнуть воду)

• Высота u больше высоты v на 1: h[u] = h[v] + 1

Это как если бы вода могла течь только «вниз по лестнице» — на одну ступеньку за раз.

2. Идея алгоритма: «Накачай и выдавливай»

Алгоритм проталкивания предпотока работает по принципу:

1. Инициализация:

• Устанавливаем высоту истока равной количеству вершин n

• Все остальные вершины получают высоту 0

• «Накачиваем» из истока максимальный поток во все соседние вершины

• Теперь в некоторых вершинах есть избыточный поток

2. Основной цикл: Пока есть вершины с избыточным потоком (кроме истока и стока):

• Выбираем любую такую вершину

• Пытаемся протолкнуть избыточный поток в соседние вершины

• Если протолкнуть не получается, поднимаем высоту вершины

3. Завершение: Когда избыточного потока больше нет, весь поток, который дошёл до стока, и есть максимальный поток.

Представьте, что вы в горах с ведром воды. Вы можете вылить воду только в том случае, если рядом есть место пониже. Если все места вокруг выше или равны по высоте, вы поднимаетесь на камень повыше и пробуете снова. Рано или поздно вода найдёт путь вниз к морю (стоку).

3. Операции Push и Relabel

Алгоритм использует две основные операции:

Push (Проталкивание)

Условие: у вершины u есть избыточный поток,           есть допустимое ребро u → v Действие: проталкиваем min(excess[u], capacity[u→v]) единиц потока

Это как если бы вы взяли часть воды из переполненного ведра и вылили её в соседнее ведро, которое стоит ниже и может принять воду.

Relabel (Переобозначение/Поднятие)

Условие: у вершины u есть избыточный поток,          но нет допустимых рёбер для проталкивания Действие: увеличиваем высоту u до минимальной высоты соседей + 1

Это как если бы вы встали на стул, чтобы найти место, куда можно вылить воду.

4. Пример работы алгоритма

Рассмотрим простой граф:

0 → 1 (пропускная способность 10) 0 → 2 (пропускная способность 10) 1 → 3 (пропускная способность 4) 2 → 3 (пропускная способность 10)

Исток s = 0, сток t = 3.

Инициализация:

• height[0] = 4, height[1] = height[2] = height[3] = 0

• Проталкиваем из 0: 10 в вершину 1, 10 в вершину 2

• excess[1] = 10, excess[2] = 10

Итерация 1 (обрабатываем вершину 1):

• excess[1] = 10, height[1] = 0

• Смотрим ребро 1 → 3: height[1] = 0, height[3] = 0

• Ребро не допустимо (нужно height[1] = height[3] + 1)

• Relabel: height[1] = height[3] + 1 = 1

• Теперь ребро 1 → 3 допустимо

• Push: проталкиваем min(10, 4) = 4 единицы в вершину 3

• excess[1] = 6, excess[3] = 4

Итерация 2 (обрабатываем вершину 2):

• excess[2] = 10, height[2] = 0

• Ребро 2 → 3 допустимо (height[2] = 0, height[3] = 0, но нужно height[2] = height[3] + 1)

• Relabel: height[2] = 1

• Push: проталкиваем min(10, 10) = 10 единиц в вершину 3

• excess[2] = 0, excess[3] = 14

Итерация 3 (обрабатываем вершину 1):

• excess[1] = 6, height[1] = 1

• Ребро 1 → 3 больше не допустимо (height[1] = 1, height[3] = 0, но пропускная способность = 0)

• Нет других рёбер из 1

• Relabel: height[1] = 2

• Но из 1 всё ещё нельзя ничего протолкнуть

• Вода «застряла» в вершине 1

Алгоритм продолжается, пока весь избыточный поток не будет либо доставлен в сток, либо возвращён в исток.

5. Код на C# с подробными комментариями

// Алгоритм проталкивания предпотока (Push-Relabel)  using System; using System.Collections.Generic; using System.Linq;  namespace PushRelabelMaxFlow {     /// <summary>Структура ребра для алгоритма проталкивания предпотока.</summary>     public class Edge     {         public int To;      // куда ведёт ребро         public int Rev;     // индекс обратного ребра         public long Cap;    // остаточная пропускная способность         public long Flow;   // текущий поток          public Edge(int to, int rev, long cap)         {             To = to;             Rev = rev;             Cap = cap;             Flow = 0;         }     }      /// <summary>Реализация алгоритма проталкивания предпотока.</summary>     public class PushRelabel     {         private readonly List<Edge>[] _graph;         private readonly int _n;         private long[] _excess;     // избыточный поток в каждой вершине         private int[] _height;      // высота каждой вершины         private Queue<int> _active; // очередь активных вершин (с избыточным потоком)          public PushRelabel(int n)         {             _n = n;             _graph = new List<Edge>[n];             for (int i = 0; i < n; i++)                 _graph[i] = new List<Edge>();                          _excess = new long[n];             _height = new int[n];             _active = new Queue<int>();         }          /// <summary>Добавляет ребро from → to с пропускной способностью cap.</summary>         public void AddEdge(int from, int to, long cap)         {             // Прямое ребро             Edge forward = new Edge(to, _graph[to].Count, cap);             // Обратное ребро с нулевой пропускной способностью             Edge backward = new Edge(from, _graph[from].Count, 0);                          _graph[from].Add(forward);             _graph[to].Add(backward);         }          /// <summary>Находит максимальный поток от источника source к стоку sink.</summary>         public long MaxFlow(int source, int sink)         {             // Инициализация             InitializePreflow(source);                          // Основной цикл: обрабатываем активные вершины             while (_active.Count > 0)             {                 int u = _active.Dequeue();                                  // Если в вершине всё ещё есть избыточный поток                 if (_excess[u] > 0)                 {                     // Пытаемся протолкнуть поток или поднять высоту                     if (!PushFlow(u, sink))                     {                         Relabel(u);                         // После поднятия высоты вершина снова становится активной                         if (_excess[u] > 0)                             _active.Enqueue(u);                     }                 }             }                          // Максимальный поток равен избыточному потоку в стоке             return _excess[sink];         }          /// <summary>Инициализирует предпоток: "накачивает" воду из источника.</summary>         private void InitializePreflow(int source)         {             // Источник получает максимальную высоту             _height[source] = _n;                          // Проталкиваем максимальный поток из источника во все соседние вершины             foreach (var edge in _graph[source])             {                 if (edge.Cap > 0)                 {                     // Отправляем всю доступную пропускную способность                     long flow = edge.Cap;                     edge.Flow += flow;                     edge.Cap -= flow;                                          // Увеличиваем пропускную способность обратного ребра                     _graph[edge.To][edge.Rev].Cap += flow;                                          // Создаём избыточный поток в целевой вершине                     _excess[edge.To] += flow;                     _excess[source] -= flow;                                          // Если целевая вершина получила избыточный поток, делаем её активной                     if (_excess[edge.To] > 0 && edge.To != source)                     {                         _active.Enqueue(edge.To);                     }                 }             }         }          /// <summary>Пытается протолкнуть поток из вершины u. Возвращает true, если удалось.</summary>         private bool PushFlow(int u, int sink)         {             foreach (var edge in _graph[u])             {                 // Проверяем, является ли ребро допустимым                 if (edge.Cap > 0 && _height[u] == _height[edge.To] + 1)                 {                     // Вычисляем количество потока для проталкивания                     long pushFlow = Math.Min(_excess[u], edge.Cap);                                          // Обновляем поток и пропускные способности                     edge.Flow += pushFlow;                     edge.Cap -= pushFlow;                     _graph[edge.To][edge.Rev].Cap += pushFlow;                                          // Обновляем избыточные потоки                     _excess[u] -= pushFlow;                     _excess[edge.To] += pushFlow;                                          // Если целевая вершина получила избыточный поток и это не сток,                     // добавляем её в очередь активных вершин                     if (_excess[edge.To] == pushFlow && edge.To != sink)                     {                         _active.Enqueue(edge.To);                     }                                          // Если весь избыточный поток протолкнут, возвращаем true                     if (_excess[u] == 0)                         return true;                 }             }                          return false; // Не удалось протолкнуть поток         }          /// <summary>Поднимает высоту вершины u.</summary>         private void Relabel(int u)         {             int minHeight = int.MaxValue;                          // Находим минимальную высоту среди соседей с доступной пропускной способностью             foreach (var edge in _graph[u])             {                 if (edge.Cap > 0)                 {                     minHeight = Math.Min(minHeight, _height[edge.To]);                 }             }                          // Поднимаем высоту на 1 выше минимальной найденной             if (minHeight != int.MaxValue)             {                 _height[u] = minHeight + 1;             }         }          /// <summary>Выводит текущее состояние для отладки.</summary>         public void PrintState()         {             Console.WriteLine("Текущее состояние:");             Console.WriteLine("Вершина | Высота | Избыток");             Console.WriteLine("--------|--------|--------");             for (int i = 0; i < _n; i++)             {                 Console.WriteLine($"   {i}    |   {_height[i]}    |   {_excess[i]}");             }             Console.WriteLine();         }     }      internal static class Program     {         private static void Main()         {             // Создаём граф с 4 вершинами             int n = 4;             PushRelabel pr = new PushRelabel(n);              // Добавляем рёбра с пропускными способностями             pr.AddEdge(0, 1, 10);  // от 0 к 1, пропускная способность 10             pr.AddEdge(0, 2, 10);  // от 0 к 2, пропускная способность 10             pr.AddEdge(1, 3, 4);   // от 1 к 3, пропускная способность 4             pr.AddEdge(2, 3, 10);  // от 2 к 3, пропускная способность 10              Console.WriteLine("Поиск максимального потока...");                          // Находим максимальный поток от вершины 0 к вершине 3             long maxFlow = pr.MaxFlow(0, 3);                          Console.WriteLine($"Максимальный поток = {maxFlow}");                          // Выводим финальное состояние             pr.PrintState();         }     } }

6. Сравнение с другими алгоритмами

Вы можете спросить: «А зачем нужен ещё один алгоритм максимального потока?» Отличный вопрос!

Форд-Фалкерсон: Простой и понятный, но может работать медленно на некоторых графах. Это как идти пешком — надёжно, но не быстро.

Диниц: Быстрый и эффективный, но требует построения уровневых графов. Это как ехать на машине по навигатору — быстро, но нужно планировать маршрут.

Проталкивание предпотока: Работает «локально» — каждая вершина решает свои проблемы независимо. Это как система автоматического полива — каждая секция работает самостоятельно, но в итоге весь сад политый.

Преимущества Push‑Relabel:

• Хорошо параллелится (разные вершины можно обрабатывать одновременно)

• Стабильная производительность на разных типах графов

• Легко модифицируется для специальных задач

Недостатки:

• Сложнее для понимания новичкам

• Требует больше памяти для хранения высот и избыточных потоков

• Может создавать «промежуточные» состояния с большим количеством избыточного потока

7. Заключение

Алгоритм проталкивания предпотока — это элегантный пример того, как можно решить задачу, подойдя к ней с совершенно другой стороны. Вместо поиска путей мы «накачиваем давление» и позволяем потоку найти оптимальное распределение самостоятельно.

Этот подход не только красив теоретически, но и практически полезен. Он лежит в основе многих современных алгоритмов компьютерного зрения, используется в системах управления трафиком и помогает решать задачи оптимизации в реальном времени.

Главное — не пугайтесь новых концепций вроде «предпотока» и «высот». За каждым термином стоит простая физическая интуиция: вода течёт сверху вниз, и если где‑то её слишком много, она найдёт способ стечь дальше. Алгоритм просто формализует эту интуицию и превращает её в точные правила.

Помните: лучший способ понять любой алгоритм — взять простой пример и проследить его выполнение шаг за шагом. Нарисуйте граф, поставьте высоты, начните «проталкивать» поток, и вы увидите, как абстрактные правила превращаются в понятные действия.

Удачи в изучении алгоритмов! И не забывайте: каждый сложный алгоритм — это просто набор простых идей, собранных вместе. Главное — не торопиться и разбирать по одной идее за раз.