Где применяется
1. Задача
Есть несколько городов и список дорог, которые между ними можно построить. У каждой дороги своя цена. Нужно связать все города и заплатить в сумме как можно меньше. Такой набор дорог называют минимальным остовным деревом (minimum spanning tree, MST). Оно доходит до каждого города, в нём нет петель, а сумма цен его дорог наименьшая из возможных.
В прошлом уроке ту же задачу решал алгоритм Краскала. Он сортировал все дороги на карте от самой дешёвой к самой дорогой. Дорогу он брал, если она соединяла два ещё не связанных города. Проверку «уже связаны?» он делал через union-find.
Прим идёт с другой стороны. Он растит одно дерево из одного стартового города и всю карту сразу не просматривает. На каждом шаге он смотрит только на дороги, которые выходят из уже подключённых городов, и берёт самую дешёвую из тех, что ведут в новый город. На связном графе он получает ту же сумму, что и Краскал.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где связную область наращивают от одной точки, каждый раз беря самое дешёвое ребро наружу, например строят самую дешёвую сеть или заливают сетку с самого низкого края. Прим держит эти рёбра в мин-куче и пропускает уже взятые узлы.
Каждая пара точек это ребро, и на таком плотном графе Приму не нужен заранее список всех рёбер.
Расти от левой верхней клетки, всегда беря самую низкую клетку на границе, и ответ равен самой высокой взятой клетке к моменту, когда ты дошёл до угла.
Положи в мин-кучу все клетки на краю, доставай самую низкую стенку и наливай воду во внутреннего соседа до её высоты.