Привет, будущие инженеры и программисты! Сегодня мы разберём ещё один крутой алгоритм для поиска максимального потока — алгоритм проталкивания предпотока (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. Заключение

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

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

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

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

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

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