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

альтернативный текст

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


graph algorithm prims-algorithm minimum-spanning-tree
person devoidfeast    schedule 30.12.2010    source источник
comment
Какую часть алгоритма Прима вы не понимаете?   -  person Fred Foo    schedule 30.12.2010
comment
да, я понимаю алгоритм prims, но в ненаправленном графике.   -  person devoidfeast    schedule 30.12.2010
comment
ориентированный граф является проблемой для меня здесь.   -  person devoidfeast    schedule 30.12.2010
comment
@Programming_Kills Почему вы не упомянули эту важную деталь в вопросе? См. это.   -  person moinudin    schedule 30.12.2010
comment
Я написал учебник о том, как реализовать алгоритм prim на С++, вы можете проверить его, возможно, это поможет: cedricve.me/2012/05/15/c-prims-algorithm   -  person    schedule 16.05.2012

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

person moinudin    schedule 30.12.2010