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

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

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

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

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

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

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

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

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

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

Elysia Tools

Навигация

Math & Numbers

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

Строит минимальное остовное дерево неориентированного взвешенного графа (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 отклонено за цикл.

Запуск

Запустить этот инструмент

Заполните форму, запустите инструмент и посмотрите результат на этой же странице.

Примеры

Примеры для этого инструмента

Связано

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

Запустить этот инструмент

Примеры для этого инструмента

Продолжить с похожими инструментами и темами

Узнайте, когда использовать этот инструмент, что он поддерживает и как его применяют пользователи.

Ключевые факты

Обзор

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

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

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

Примеры

1. Построение МОД алгоритмом Краскала с фиксацией циклов

2. Проектирование подключения узлов методом Прима

FAQ

Примеры Обработки Изображений Web Python

SVG Примеры

Примеры Обработки Изображений Android Java

Примеры Обработки Изображений Android Kotlin

Калькулятор плотности (ρ = m/V)

Калькулятор NPSH насоса (доступного кавитационного запаса) и проверка на кавитацию

Слова в Число

Адаптивный скрытый водяной знак в 12 точках