Генерал требовал соединять любые две воинские части напрямую на случай ядерной зимы, и с тех пор имя генерала нарицательно для транжирства. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует алгоритмы Краскала и Прима, которые находят самую дешёвую сеть без лишних линий связи, в трёх нотациях.

Рис. 1. Схема по ГОСТ 19.701: связи по возрастанию цены и без петель
В институтские годы слышал байку о генерале, требовавшем соединять каждую воинскую часть с каждой на случай ядерной зимы. Когда пришли проверять расходы, оказалось, что переплата составила астрономические суммы.
Учитывая боевые заслуги и родственные связи, старичка отпустили на покой, но имя сделали нарицательным для транжирства, хоть и ради благой цели.
Короткий ответ: алгоритмы Краскала и Прима находят самую дешёвую сеть, которая объединяет все объекты без лишних линий: трасс в ней на одну меньше, чем объектов.
Рисовать такую сеть руководителю удобнее всего графом с ценой каждого кабеля.
Что ищут алгоритмы?
Остовное дерево – способ связать все объекты без петель: между любыми двумя есть ровно один путь. Самое дешёвое из таких деревьев называют минимальным.
Как растёт сеть по кусочкам?
Алгоритм Краскала – способ строить дерево с самых дешёвых трасс. Трассы упорядочивают по цене и берут по одной, если они соединяют разные островки; трассу внутри островка пропускают – она дала бы петлю.
Остановка – когда линий на одну меньше, чем площадок. По ГОСТ 19.701 – сортировка, цикл перебора и ромб проверки концов.
Джозеф Краскал опубликовал метод в 1956 году, Роберт Прим из Bell Labs – второй в 1957-м. А первым задачу решил Отакар Борувка в 1926 году для электрификации юга Моравии.
Как это выглядит на деле?
Сервисная компания «Кедр» связывает кабелем диспетчеризации шесть объектов: базу, склад, цех, мастерскую, насосную и котельную. Десять возможных трасс стоят 6,5 миллиона рублей.

Рис. 2. Экономная сеть из пяти линий на карте площадок
Краскал берёт трассы от дешёвой к дорогой и пропускает склад – насосную: они уже на одном островке. Итог – 2,1 миллиона за всю сеть, втрое дешевле, чем тянуть всё подряд.

Рис. 3. Шесть решений в порядке роста цены
Чем отличается второй алгоритм?
Алгоритм Прима – способ растить дерево от площадки самой дешёвой трассой наружу.
В регионе планировалась сеть однотипных объектов обслуживания населения. Начался спор, как соединять сети: компьютерную, контроля доступа, пожарную и охранную сигнализацию.
Задача осложнялась тем, что малые площадки строились быстрее, чем крупные, которые должны были стать узлами сети.
Краскал здесь удобнее: он соединяет островки, где бы они ни появились, и не ждёт главного узла. Прим хорош, когда центр уже стоит: к готовой части каждый раз добавляют самую дешёвую трассу наружу, у «Кедра» – начиная с базы.

Рис. 4. Оба алгоритма в несколько строк
Почему экономная сеть хрупкая?
В одной европейской стране в разгар рабочего дня перестали работать платёжные карты – и Visa, и Mastercard. Когда стали разбираться, оказалось, что в ходе оптимизации и без того малопропускных каналов обе платёжные системы пустили «по одному проводу».
Кто бы мог подумать: интернет задумывали как сеть, которая переживёт потерю любого узла.
В дереве между двумя объектами ровно один путь, поэтому обрыв трассы разрезает сеть надвое. Для важных связей добавляют резервные трассы – осознанно, а не «каждый с каждым».
Когда хватает простого?
В середине 90-х пришёл на проект в компанию и поинтересовался, есть ли у них компьютерная сеть. ИТ-шник на полном серьёзе показал на иконку «Вся сеть»: это всё, что у них есть.
Бюджет на километры витой пары сразу не выделили, зато между офисами ездили машины. Обязал водителей забирать трёхдюймовые дискеты: не мгновенная связь, зато регулярная.
Готовые маршруты – трассы почти нулевой цены: дешёвое дерево строят прежде всего из них, а новые линии тянут только туда, куда транспорт не ходит.
Сколько стоит расчёт?
Модель: у 100 объектов возможных трасс «каждый с каждым» – 4’950, а различных деревьев – число из 197 цифр, перебор невозможен.
Краскалу достаточно упорядочить варианты: около 61 тысячи сравнений. Вручную по 10 секунд на сравнение – 170 часов, компьютер справляется за миллисекунды.
Когда уместны алгоритмы?
Там, где нужно связать все объекты дешевле всего: кабели и трубы, каналы связи, маршруты курьеров между филиалами, сигнализация.
Краскал – если площадки появляются островками, Прим – если сеть растёт от центра.
В следующей статье сборника – максимальный поток: сколько заявок, денег или грузов пропустит сеть с узкими местами.
Какими нотациями рисовать сеть?
ГОСТ 19.701 передаёт сортировку, цикл и проверку на петлю, его ценят аудиторы и авторы регламентов: каждое решение видно отдельным блоком.
Граф с ценами трасс показывает все варианты и выбранное дерево сразу. Его любят руководители и инженеры: видно, какие трассы отброшены и почему.
Псевдокод – способ записать алгоритм короткими строками на обычном языке. Им пользуются разработчики и ИИ: восемь строк Краскала и семь строк Прима читаются без потерь.
Какая нотация лучше?
Лучшая нотация для самой дешёвой сети – граф с ценами трасс: 21 балл против 18 у псевдокода и 16 у ГОСТ. Руководитель за минуту видит, какие трассы взяты и какие отброшены. Вес вопроса о руководителе удвоен: сборник написан для него.

Рис. 5. Оценка трёх нотаций: 16, 21 и 18 баллов
Псевдокод отстал на три балла и нужен тем, кто будет программировать расчёт для сотен площадок и тысяч трасс.
ГОСТ остаётся для регламентов и аудита, где важна каждая проверка.
Что сделать руководителю?
Хватит четырёх шагов:
- Перечислите объекты и все возможные трассы с ценой прокладки и последующего обслуживания линий.
- Включите в список готовые маршруты: машины, курьеров, общие каналы, у которых цена новой связи почти нулевая.
- Постройте дерево Краскалом или Примом и сравните с планом «каждый с каждым» по цене, срокам и числу трасс.
- Добавьте резерв только там, где обрыв остановит деньги или безопасность.
Что запомнить?
- остовное дерево связывает все объекты без петель
- Краскал сливает островки от дешёвых трасс к дорогим
- Прим растит сеть от одного центра
- у экономной сети нет резерва – его добавляют осознанно
- дешёвую сеть лучше всего рисовать графом с ценами трасс.