Finding MST направленного графа с использованием алгоритма Прима

Question

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

Answer 1

Цитирование The Directed Minimum Spanning Tree Problem:

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

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