Нахождение MST ориентированного графа по алгоритму Прима

Question

Может ли кто-нибудь PLZ помочь мне, как найти MST, используя алгоритм PRIM. Выделите края MST и запишите последовательность, в которой узлы добавляются в MST. спасибо

Answer 1

Цитирование Задача минимального связующего дерева :

1. Откажитесь от дуг, входящих в корень, если таковые имеются; Для каждого узла, кроме корень, выберите входящую дугу с помощью наименьшая стоимость; Пусть выбран н-1 дуги быть множеством S.
2. Если цикл не сформирован, G (N, S) является MST. В противном случае продолжайте.
3. Для каждого сформированного цикла сжимайте узлы в цикле в псевдоузел (k) и изменить стоимость каждой дуги который входит в узел (J) в цикле из некоторого узла (I) вне цикла согласно следующему уравнению.
   с (I, K) = C (I, J) - (с (х (к), J) -min_ {J} (с (х (J), J)) здесь c (x (j), j) - стоимость дуги в цикле, который входит в J.
4. Для каждого псевдоузла выберите входящую дугу с наименьшей модифицированная стоимость; Заменить дугу, которая входит в тот же реальный узел в S новая выбранная дуга.
5. Перейдите к шагу 2 с графиком сокращения.

Основная идея алгоритма заключается в найти заменяющую дугу (и), которая имеет минимальные дополнительные расходы на устранение цикл (ы), если таковые имеются. Данное уравнение показывает связанные дополнительные расходы.