Публикация Школы траблшутеров

Алгоритмы Краскала и Прима: как связать все объекты самой дешёвой сетью

Время чтения: 6 мин 35 сек
11 ноября 2026 Просмотров: 11

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

Алгоритмы Краскала и Прима: как связать все объекты самой дешёвой сетью

Рис. 1. Схема по ГОСТ 19.701: связи по возрастанию цены и без петель

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

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

Короткий ответ: алгоритмы Краскала и Прима находят самую дешёвую сеть, которая объединяет все объекты без лишних линий: трасс в ней на одну меньше, чем объектов.

Рисовать такую сеть руководителю удобнее всего графом с ценой каждого кабеля.

Что ищут алгоритмы?

Остовное дерево – способ связать все объекты без петель: между любыми двумя есть ровно один путь. Самое дешёвое из таких деревьев называют минимальным.

Как растёт сеть по кусочкам?

Алгоритм Краскала – способ строить дерево с самых дешёвых трасс. Трассы упорядочивают по цене и берут по одной, если они соединяют разные островки; трассу внутри островка пропускают – она дала бы петлю.

Остановка – когда линий на одну меньше, чем площадок. По ГОСТ 19.701 – сортировка, цикл перебора и ромб проверки концов.

Джозеф Краскал опубликовал метод в 1956 году, Роберт Прим из Bell Labs – второй в 1957-м. А первым задачу решил Отакар Борувка в 1926 году для электрификации юга Моравии.

Как это выглядит на деле?

Сервисная компания «Кедр» связывает кабелем диспетчеризации шесть объектов: базу, склад, цех, мастерскую, насосную и котельную. Десять возможных трасс стоят 6,5 миллиона рублей.

image html

Рис. 2. Экономная сеть из пяти линий на карте площадок

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

image html

Рис. 3. Шесть решений в порядке роста цены

Чем отличается второй алгоритм?

Алгоритм Прима – способ растить дерево от площадки самой дешёвой трассой наружу.

В регионе планировалась сеть однотипных объектов обслуживания населения. Начался спор, как соединять сети: компьютерную, контроля доступа, пожарную и охранную сигнализацию.

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

Краскал здесь удобнее: он соединяет островки, где бы они ни появились, и не ждёт главного узла. Прим хорош, когда центр уже стоит: к готовой части каждый раз добавляют самую дешёвую трассу наружу, у «Кедра» – начиная с базы.

image html

Рис. 4. Оба алгоритма в несколько строк

Почему экономная сеть хрупкая?

В одной европейской стране в разгар рабочего дня перестали работать платёжные карты – и Visa, и Mastercard. Когда стали разбираться, оказалось, что в ходе оптимизации и без того малопропускных каналов обе платёжные системы пустили «по одному проводу».

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

В дереве между двумя объектами ровно один путь, поэтому обрыв трассы разрезает сеть надвое. Для важных связей добавляют резервные трассы – осознанно, а не «каждый с каждым».

Когда хватает простого?

В середине 90-х пришёл на проект в компанию и поинтересовался, есть ли у них компьютерная сеть. ИТ-шник на полном серьёзе показал на иконку «Вся сеть»: это всё, что у них есть.

Бюджет на километры витой пары сразу не выделили, зато между офисами ездили машины. Обязал водителей забирать трёхдюймовые дискеты: не мгновенная связь, зато регулярная.

Готовые маршруты – трассы почти нулевой цены: дешёвое дерево строят прежде всего из них, а новые линии тянут только туда, куда транспорт не ходит.

Сколько стоит расчёт?

Модель: у 100 объектов возможных трасс «каждый с каждым» – 4’950, а различных деревьев – число из 197 цифр, перебор невозможен.

Краскалу достаточно упорядочить варианты: около 61 тысячи сравнений. Вручную по 10 секунд на сравнение – 170 часов, компьютер справляется за миллисекунды.

Когда уместны алгоритмы?

Там, где нужно связать все объекты дешевле всего: кабели и трубы, каналы связи, маршруты курьеров между филиалами, сигнализация.

Краскал – если площадки появляются островками, Прим – если сеть растёт от центра.

В следующей статье сборника – максимальный поток: сколько заявок, денег или грузов пропустит сеть с узкими местами.

Какими нотациями рисовать сеть?

ГОСТ 19.701 передаёт сортировку, цикл и проверку на петлю, его ценят аудиторы и авторы регламентов: каждое решение видно отдельным блоком.

Граф с ценами трасс показывает все варианты и выбранное дерево сразу. Его любят руководители и инженеры: видно, какие трассы отброшены и почему.

Псевдокод – способ записать алгоритм короткими строками на обычном языке. Им пользуются разработчики и ИИ: восемь строк Краскала и семь строк Прима читаются без потерь.

Какая нотация лучше?

Лучшая нотация для самой дешёвой сети – граф с ценами трасс: 21 балл против 18 у псевдокода и 16 у ГОСТ. Руководитель за минуту видит, какие трассы взяты и какие отброшены. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 5. Оценка трёх нотаций: 16, 21 и 18 баллов

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

ГОСТ остаётся для регламентов и аудита, где важна каждая проверка.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Перечислите объекты и все возможные трассы с ценой прокладки и последующего обслуживания линий.
  2. Включите в список готовые маршруты: машины, курьеров, общие каналы, у которых цена новой связи почти нулевая.
  3. Постройте дерево Краскалом или Примом и сравните с планом «каждый с каждым» по цене, срокам и числу трасс.
  4. Добавьте резерв только там, где обрыв остановит деньги или безопасность.

Что запомнить?

  • остовное дерево связывает все объекты без петель
  • Краскал сливает островки от дешёвых трасс к дорогим
  • Прим растит сеть от одного центра
  • у экономной сети нет резерва – его добавляют осознанно
  • дешёвую сеть лучше всего рисовать графом с ценами трасс.