# Калькулятор минимального остовного дерева (Краскал / Прим)

Строит минимальное остовное дерево неориентированного взвешенного графа (1–30 рёбер, по одному на строку: узел1, узел2, вес) двумя алгоритмами: Краскал сортирует рёбра по весу и проверяет их структурой непересекающихся множеств, протоколируя каждое принятое ребро и каждое отклонённое за цикл; Прим стартует с начального узла и на каждом шаге берёт самое дешёвое ребро, покидающее компоненту, показывая её рост. Петли пропускаются; несвязный граф отклоняется с указанием числа компонент; итоговые веса обоих алгоритмов обязаны совпасть (внутренняя проверка). Классика: A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, D-E 4, D-F 11, E-F 8 → вес МОД 21 (A—C, C—E, A—B, D—E, E—F), ребро B—C отклонено за цикл.

> Каноническая страница: https://elysiatools.com/ru/tools/minimum-spanning-tree

- **Категория:** Math & Numbers

- **Ключевые слова:** минимальное остовное дерево, мод, краскал, прим, непересекающиеся множества, жадный алгоритм, граф, проектирование сетей, остовное дерево, дискретная математика

## Обзор

Онлайн-калькулятор минимального остовного дерева (МОД) строит остов для взвешенных неориентированных графов с помощью алгоритмов Краскала и Прима. Инструмент выполняет пошаговую трассировку: логирует добавление и отклонение рёбер из-за циклов, отслеживает расширение компонент связности и проверяет равенство итогового веса дерева между обоими методами.

## Входные данные

- **Рёбра (по одному на строку: узел1, узел2, вес)** (textarea): One undirected edge per line: two node names (1–8 letters/digits) and a weight (negatives allowed).
- **Алгоритм** (select)
- **Начальный узел (только для Прима, необязательно)** (text): e.g. D
- **Знаков после запятой** (number)

## Когда использовать

- Для решения учебных задач по дискретной математике и теории графов с пошаговой проверкой алгоритмов Краскала и Прима.
- При проектировании кабельных трасс, трубопроводов или локальных сетей с минимальной суммарной стоимостью соединений.
- Для поиска циклов и избыточных связей в топологиях взвешенных неориентированных графов.

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

- Введите список рёбер графа (по одному в строке: два имени узлов и вес), выберите желаемый алгоритм и при необходимости укажите стартовый узел для метода Прима.
- При выборе алгоритма Краскала инструмент сортирует рёбра по возрастанию веса и с помощью системы непересекающихся множеств (DSU) проверяет каждое ребро на образование цикла.
- При выборе алгоритма Прима построение начинается с указанного узла, последовательно присоединяя наименее весомое ребро, соединяющее растущее дерево с оставшимися вершинами.
- Калькулятор формирует список включённых рёбер, суммарный вес МОД и подробный журнал шагов, пропуская петли и проверяя связность графа.

## Сценарии использования

- Оптимизация сетевых магистралей и раскладки коммуникаций между узлами с минимальной суммарной длиной линий.
- Пошаговая проверка лабораторных и расчетно-графических работ по алгоритмам на графах.
- Анализ топологии распределённых систем для исключения циклических зависимостей при сохранении полной связности.

## Частые вопросы

### В каком формате нужно вводить рёбра графа?

Каждое ребро указывается на новой строке через пробел: имя первой вершины, имя второй вершины и вес (например, «A B 4» или «1 2 3.5»).

### Чем отличается вывод алгоритма Краскала от алгоритма Прима?

Краскал выводит список отсортированных рёбер со статусом (принято/отклонено из-за цикла), а Прим пошагово показывает расширение множества вершин дерева от стартовой точки.

### Что произойдёт, если граф окажется несвязным?

Калькулятор сообщит об ошибке построения МОД и выведет количество обнаруженных изолированных компонент связности.

### Поддерживаются ли отрицательные веса рёбер и петли?

Да, отрицательные веса корректно обрабатываются обоими алгоритмами, а петли (рёбра из вершины в саму себя) автоматически игнорируются.

### Всегда ли совпадают наборы рёбер у Краскала и Прима?

Итоговый суммарный вес всегда совпадает, однако при наличии рёбер с одинаковым весом конкретные наборы выбранных рёбер могут отличаться.

## Связанные инструменты

- [Калькулятор плотности (ρ = m/V)](https://elysiatools.com/ru/tools/density-calculator): Находит плотность, массу или объём по двум другим, с удельной плотностью и плавучестью
- [Калькулятор NPSH насоса (доступного кавитационного запаса) и проверка на кавитацию](https://elysiatools.com/ru/tools/pump-npsh-calculator): Расчёт доступного кавитационного запаса насоса: NPSH_a = (p_surface - p_vapor)/(ρ·g) + H_static - h_friction (м). Давления поверхности и пара — абсолютные; H_static положителен при подпоре (жидкость выше насоса) и отрицателен при всасывании (жидкость ниже насоса). Сравнение с NPSH_r из характеристики насоса: запас margin = NPSH_a - NPSH_r и отношение ratio = NPSH_a/NPSH_r; классификация safe (безопасно), marginal (запас < 0,5 м) или cavitation likely (вероятна кавитация). Если NPSH_r = 0, выводится только NPSH_a. Давления: Па/кПа/бар/атм/psi, длина: м/фт, плотность: кг/м³/г/см³/фунт/фт³.
- [Слова в Число](https://elysiatools.com/ru/tools/words-to-number): Преобразует числовые слова английского языка в цифры. Поддерживает порядок величин, "and", десятичные дроби через "point" и дефисы, заменяя числовой фрагмент по месту.
- [Адаптивный скрытый водяной знак в 12 точках](https://elysiatools.com/ru/tools/adaptive-12-point-hidden-watermark): Добавляет ненавязчивый текстовый водяной знак к одному изображению или ко всем поддерживаемым изображениям в ZIP, во все, случайные или выбранные точки по периметру и автоматически подбирает светлый или тёмный контраст.
- [Калькулятор фракционной экскреции натрия FENa](https://elysiatools.com/ru/tools/fractional-excretion-sodium): Фракционная экскреция натрия FENa = (Na-мочи×SCr)/(Na-сыворотки×UCr)×100%. Дифференцирует олигурическое ОПП: <1% — преренальная азотемия (гиповолемия, ХСН, гепаторенальный синдром, натрий-сберегающие состояния); ≥1% — внутрипочечное повреждение (обычно ОКН, повреждённые канальцы не реабсорбируют натрий); >4% — иногда при постренальной обструкции. Диуретики искажают результат (используйте FEUrea<35%); АКН при контрасте/сепсисе может давать низкую FENa; хроническая ХБП и глюкозурия повышают FENa. Толковать с учётом клиники. Не медицинская консультация.
- [Делитель тредов Twitter / X](https://elysiatools.com/ru/tools/twitter-thread-splitter): Вставьте длинный текст и разбейте его на нумерованный тред X, соблюдая лимит 280 символов. Деление по границам слов/предложений/абзацев, автонумерация 1/N, корректный учёт CJK и полноширинных символов, URL считаются за 23 символа, и карта в стиле X со счётчиком символов.
- [Калькулятор мощности приточной установки (охлаждение / нагрев)](https://elysiatools.com/ru/tools/ahu-capacity-calculator): Вычисляет мощность батареи приточной установки по состояниям входа/выхода и массовому расходу сухого воздуха ṁ_da: полная мощность Qt=ṁ_da·(h1−h2), явная Qs=ṁ_da·cp_ma·(T1−T2) (cp_ma≈1,006+1,86·W), скрытая Ql=Qt−Qs, SHR=Qs/Qt. Состояния задаются сухим термометром T и одним параметром влажности (отн. влажность φ или влагосодержание W); W вычисляется по формуле Магнуса, энтальпия h=1,006·T+W·(2501+1,86·T). Результат со знаком, для охлаждения или нагрева.
- [Калькулятор силы Архимеда (F = ρ·V·g)](https://elysiatools.com/ru/tools/buoyancy-calculator): Находит силу Архимеда, плотность жидкости или объём по двум из них, с анализом плавучести

## Примеры

- [Примеры Обработки Изображений Web Python](https://elysiatools.com/ru/samples/web-image-processing-python): Примеры обработки изображений Web Python используя PIL/Pillow включая чтение, сохранение, изменение размера и преобразование формата
- [SVG Примеры](https://elysiatools.com/ru/samples/svg-samples): Примеры масштабируемой векторной графики (SVG) демонстрирующие различные возможности и техники SVG
- [Примеры Обработки Изображений Android Java](https://elysiatools.com/ru/samples/android-image-processing-java): Примеры обработки изображений Android Java включая чтение/сохранение, масштабирование и преобразование формата
- [Примеры Обработки Изображений Android Kotlin](https://elysiatools.com/ru/samples/android-image-processing-kotlin): Примеры обработки изображений Android Kotlin включая чтение/сохранение, масштабирование и преобразование формата