MST Прима с кучей
Выращивайте дерево из одной вершины
«MST Прима с кучей» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Другой путь к MST
Алгоритм Прима также находит минимальное остовное дерево, но расширяет одну связную область наружу, вместо того чтобы сначала сортировать все рёбра. 🌱
Начните с одной вершины
Выберите любую начальную вершину и отметьте её как посещённую. Дерево начинается с одной вершины и расширяется по одному ребру.
visited = [False] * nИдея границы
На каждом шаге рассмотрите все рёбра, ведущие из дерева наружу. Алгоритм Прима всегда выбирает самое дешёвое из этих пограничных рёбер.
Куча выбирает минимум
Минимальная куча ускоряет поиск самого дешёвого пограничного ребра. На каждом шаге добавляйте в неё рёбра-кандидаты и извлекайте ребро с наименьшим весом.
import heapq
heap = [(0, start)]Извлеките самое дешёвое ребро
Извлеките из кучи запись с наименьшим значением. Она содержит вес и следующую вершину, которую дешевле всего присоединить к растущему дереву.
w, u = heapq.heappop(heap)Пропускайте устаревшие записи
Вершина может находиться в куче несколько раз. Если извлечённая вершина уже посещена, просто проигнорируйте её и извлеките следующую запись.
if visited[u]:
continueДобавляйте и расширяйте
Отметьте извлечённую вершину как посещённую и добавьте её вес к общей сумме. Затем добавьте в кучу все исходящие из неё рёбра для последующих шагов.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Повторяйте до полного охвата
Продолжайте извлекать вершины и расширять дерево, пока каждая вершина не будет посещена. После этого накопленная сумма станет весом минимального остовного дерева.
Время работы
Каждое ребро можно добавить в кучу и извлечь из неё один раз, поэтому алгоритм Прима на основе кучи работает за O(E log V), что сопоставимо с алгоритмом Крускала.
Прим и Крускал
Используйте алгоритм Прима для плотных графов со списком смежности, а алгоритм Крускала — когда у Вас уже есть обычный список рёбер. Оба алгоритма дают одинаковый вес MST.
Это похоже на алгоритм Дейкстры
Цикл с кучей напоминает алгоритм Дейкстры, но здесь сравниваются исходные веса рёбер, а не расстояния путей. Распознавание этого шаблона экономит время на написание программы. ⚡
Быстрая проверка
Вспомните, как алгоритм Прима выбирает следующее ребро на каждом шаге.
Повторение
Вы построили MST с помощью алгоритма Прима: начали с любой вершины, использовали минимальную кучу для добавления самого дешёвого пограничного ребра и пропускали устаревшие посещения. Отличная работа! 🎉
Изучай Coding Interview Prep с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 90
- Уроки
- 360
Часто задаваемые вопросы
Урок «MST Прима с кучей» бесплатный?
Да — полный текст урока «MST Прима с кучей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «MST Прима с кучей»?
Выращивайте дерево из одной вершины Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «MST Прима с кучей»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- DSU со сжатием путей
- Объединение по рангу и компоненты
- Минимальное остовное дерево Краскала
- MST Прима с кучей