0Pricing
Competitive Programming Academy · Урок

MST Прима с кучей

Выращивайте дерево из одной вершины

«MST Прима с кучей» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 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 с помощью алгоритма Прима: начали с любой вершины, использовали минимальную кучу для добавления самого дешёвого пограничного ребра и пропускали устаревшие посещения. Отличная работа! 🎉

Часто задаваемые вопросы

Урок «MST Прима с кучей» бесплатный?

Да — полный текст урока «MST Прима с кучей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.

Чему я научусь в уроке «MST Прима с кучей»?

Выращивайте дерево из одной вершины Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Competitive Programming Academy?

Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «MST Прима с кучей»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Competitive Programming Academy?

Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. DSU со сжатием путей
  2. Объединение по рангу и компоненты
  3. Минимальное остовное дерево Краскала
  4. MST Прима с кучей
← Назад к Competitive Programming Academy