Алгоритм Краскала онлайн

Алгоритм Краскала для графа: введите взвешенные ребра, получите минимальное остовное дерево, общий вес, выбранные ребра и шаги проверки циклов.

Список ребер с весами

Вершины

Все вершины, если есть изолированные

Формат строки: A B 4, где A и B - вершины, 4 - вес ребра. Алгоритм Краскала работает с неориентированным взвешенным графом; петли A A 5 игнорируются.

Вес минимального остовного дерева-

Выбрано ребер-

Компоненты-

Для новичка: как читать расчет

1. Сортировка Все ребра сортируются по весу от меньшего к большему.

2. Проверка цикла Ребро берется, только если оно соединяет разные компоненты.

3. Дерево Для связного графа получится ровно вершины - 1 выбранных ребер.

4. Несвязный граф Если связности нет, результатом будет минимальный остовный лес.

Передача файла

Для отправки PDF, изображения, документа или другого файла на другое устройство можно открыть страницу передачи файлов.

Открыть страницу

Что решает алгоритм Краскала

Алгоритм Краскала строит минимальное остовное дерево для неориентированного взвешенного графа. Ребра сортируются по весу, затем добавляются только те, которые не создают цикл.

Формат ввода

Каждое ребро пишите с новой строки: A B 4. Первые два значения — вершины, третье значение — вес ребра. Если вес не указан, калькулятор считает его равным 1. Для изолированных вершин заполните отдельное поле со списком вершин.

Как читать шаги

В таблице шагов видно, какие ребра были взяты, а какие пропущены из-за цикла. Если граф несвязный, вместо одного дерева получится минимальный остовный лес по компонентам.

Что решает алгоритм Краскала

Формат ввода

Как читать шаги

Связанные калькуляторы