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

Посмотреть описание

.

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

 

 

В информатике , Алгоритм Прима (также известный как Алгоритм Ярник ) является жадный алгоритмом , который находит минимальное остовное дерево для взвешенного неориентированного графа . Это означает, что он находит подмножество ребер, которое формирует дерево , включающее каждую вершину , где общий вес всех ребер в дереве минимизирован. Алгоритм строит это дерево по одной вершине за раз, из произвольной начальной вершины, на каждом шаге добавляя самое дешевое возможное соединение из дерева в другую вершину. Алгоритм был разработан в 1930 году чешским математиком Войтехом Ярником , а затем переоткрыт и переиздан компьютерными учеными Робертом К. Примом в 1957 году и Эдсгером В. Дейкстрой в 1959 году Поэтому его также иногда называют Алгоритмом Ярника , Алгоритмом Прима – Ярника , Алгоритмом Прима – Дейкстры или Алгоритмом DJP .