Зачем полный граф — разве в приложениях не бывает разреженным?

**Полный евклидов** граф — наглядная модель: теоретически можно соединить любую пару, а MST выбирает **n−1** самых дешёвых связей без циклов. В реальных сетях рёбер меньше; те же алгоритмы работают и там, но плотный случай хорошо показывает сортировку у **Краскала** и перебор кандидатов у **Прима**.

Меняется ли сам MST при смене корня у Прима?

При **неуникальных** весах может существовать **несколько** разных наборов рёбер с одним и тем же минимальным весом. Тогда разные корни (и разный порядок) могут дать **разные** MST как множества рёбер, но **суммарный вес** остаётся тем же — он сверяется с **Краскалом**.

Что означает красная пунктирная линия в режиме Краскала?

Это текущее ребро из отсортированного списка, которое **нельзя** добавить: оба конца уже в **одной** компоненте СНМ, добавление создало бы **цикл** — алгоритм его **пропускает**.

Минимальный остов (Прим и Краскал)

Случайные точки на плоскости, полный граф с евклидовыми весами: пошаговый Прим от корня или Краскал с системой непересекающихся множеств; сравнение суммарного веса.

О модели

Минимальный остов соединяет все вершины без циклов и с наименьшей суммой весов. n псевдослучайных точек на плоскости (воспроизводимо по зерну раскладки). Граф считается полным: вес ребра — евклидово расстояние между вершинами, у любого остова n−1 ребро. Прим стартует от выбранного корня и на каждом шаге добавляет минимальное ребро через разрез «уже в дереве / снаружи» (жадность по свойству разреза). Краскал сортирует все рёбра по весу (при равенстве — лексикографически по концам для детерминизма) и обходит список с СНМ: ребро принимается, если соединяет разные компоненты, и отклоняется (красная пунктирная подсветка), если замкнуло бы цикл. Итоговые суммарные веса MST у обоих алгоритмов совпадают.

Для кого: Дискретная математика и алгоритмы: жадные построения MST, свойства разреза и цикла, СНМ.

Ключевые понятия

минимальный остов (MST)
алгоритм Прима
алгоритм Краскала
свойство разреза
свойство цикла
СНМ (система непересекающихся множеств)
полный граф
евклидовы веса

Как это работает

Полный граф из n точек на плоскости с весами евклидовых расстояний: Прим наращивает остов от корня минимальным ребром через разрез; Краскал идёт по рёбрам по возрастанию веса и СНМ отбрасывает ребро, если оно замкнуло бы цикл; суммарный вес MST у обоих совпадает.

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

Зачем полный граф — разве в приложениях не бывает разреженным?: Полный евклидов граф — наглядная модель: теоретически можно соединить любую пару, а MST выбирает n−1 самых дешёвых связей без циклов. В реальных сетях рёбер меньше; те же алгоритмы работают и там, но плотный случай хорошо показывает сортировку у Краскала и перебор кандидатов у Прима.
Меняется ли сам MST при смене корня у Прима?: При неуникальных весах может существовать несколько разных наборов рёбер с одним и тем же минимальным весом. Тогда разные корни (и разный порядок) могут дать разные MST как множества рёбер, но суммарный вес остаётся тем же — он сверяется с Краскалом.
Что означает красная пунктирная линия в режиме Краскала?: Это текущее ребро из отсортированного списка, которое нельзя добавить: оба конца уже в одной компоненте СНМ, добавление создало бы цикл — алгоритм его пропускает.

Продолжите с близкими темами в этой категории — или все 48 в «Инженерия».

Вся категория →

НовоеШкольные

Генераторы лабиринтов и A*

Запустить симулятор

Идеальные лабиринты на сетке 40×28: рекурсивный обход, Уилсон, Эллер или случайный Прим; решение A* (Манхэттен, 4-соседство). Дорисовывайте стены и переносите старт и цель.

НовоеШкольные