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

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

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

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

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

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

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

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

О модели

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

Для кого: Дискретная математика и алгоритмы: связь жадных построений MST с аргументами разреза и цикла; удобно рядом с лекцией про union–find.

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

Минимальный остов (MST)
Алгоритм Прима
Алгоритм Краскала
Свойство разреза
Свойство цикла
СНМ (union–find)
Полный граф
Евклидовы веса

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

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

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

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

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

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

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

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

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

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

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

A* / Дейкстра (сетка)

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

Интерактивная сетка 40×28: A*, Дейкстра или жадный best-first; эвристики, 4/8-связность, стены и дорогие клетки; раскраска open/closed.

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

Конечный автомат

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

Автомат Мура для светофора: цикл зелёный–жёлтый–красный по таймеру или ручное переключение; граф состояний.

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

Планировщик RRT (сетка)

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

Та же карта стен 40×28: случайные образцы, ближайший узел, шаг с проверкой столкновений, смещение выборки к цели; кнопка сравнения с A* (Манхэттен, 4-связность).

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

Обратная кинематика двухзвенного манипулятора (2R)

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

Планарное плечо из двух звеньев: цель на экране, два решения — «локоть вверх» / «локоть вниз», углы θ₁ и θ₂.

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

Прогиб балки: метод единичной силы

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

Шарнирно опёртая балка Euler-Bernoulli с силой P и нагрузкой w: closed-form прогиб против интеграла virtual work ∫Mm/EI dx.

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

О модели

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

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

Похожие симуляторы

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

A* / Дейкстра (сетка)

Конечный автомат

Планировщик RRT (сетка)

Обратная кинематика двухзвенного манипулятора (2R)

Прогиб балки: метод единичной силы

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

О модели

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

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