Минимальное остовное дерево алгоритмом Прима онлайн на Intellect

Воспользовались 531 раз

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

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

Вы можете повторно ввести значения и заново вычислить решение. Симметричные значения заполняются автоматически, но при необходимости их можно изменить вручную. Расчет всегда начинается с первой строки. Используемые ребра выделяются красным цветом. Если граф не связный, минимальное остовное дерево не будет найдено.

Описание

Введите размерность матрицы.
Заполните матрицу весов для вашего графа.
Нажмите "Запустить Prim".
Проверьте выделенные ребра минимального остовного дерева и общий вес.

Пример расчета и преобразования графа в матрицу:

В информатике алгоритм Прима, также известный как алгоритм Ярника, является жадным алгоритмом, который находит минимальное остовное дерево для взвешенного неориентированного графа. Он выбирает подмножество ребер, формирующее дерево со всеми вершинами, где суммарный вес ребер минимален.

Помог ли вам этот ответ?

Нажмите оценку и напишите коротко почему. Так мы сможем сделать следующие ответы точнее и полезнее.

Насколько вы довольны ответом?

Ваш отзыв напрямую влияет на качество следующих подсказок и ответов.

Ваш вариант ответа для данного сервиса или заметили ошибку:

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

Алгоритмы Программирование