Алгоритм Прима для графа: введите взвешенные ребра, получите минимальное остовное дерево, общий вес, выбранные ребра и шаги расчета.
Вершины и старт
Формат строки: A B 4, где A и B - вершины, 4 - вес ребра. Алгоритм Прима применяется к неориентированному взвешенному графу; петли вида A A 5 игнорируются.
Для новичка: как читать расчет
Что решает алгоритм Прима
Алгоритм Прима строит минимальное остовное дерево для неориентированного взвешенного графа. Результат показывает, какие ребра соединяют все вершины с минимальной суммой весов без циклов.
Формат ввода
Каждое ребро пишите с новой строки: A B 4. Первые два значения — вершины, третье значение — вес ребра. Если вес не указан, калькулятор считает его равным 1. Для изолированных вершин заполните отдельное поле со списком вершин.
Как читать шаги
На каждом шаге алгоритм выбирает самое легкое ребро, которое ведет из уже подключенной части графа к новой вершине. Если граф несвязный, вместо одного дерева получится минимальный остовный лес по отдельным компонентам.