Намиране на MST на насочен граф с помощта на алгоритъма на Prim

алтернативен текст

Може ли някой да ми помогне, моля, как да намеря MST с помощта на алгоритъма PRIM. Маркирайте краищата на MST и напишете последователността, в която възлите се добавят към MST.. благодаря


graph algorithm prims-algorithm minimum-spanning-tree
person devoidfeast    schedule 30.12.2010    source източник
comment
Коя част от алгоритъма на Prim не разбирате?   -  person Fred Foo    schedule 30.12.2010
comment
да, разбирам алгоритъма на prims, но в ненасочен grafgh.   -  person devoidfeast    schedule 30.12.2010
comment
насочената графа е проблем за мен тук.   -  person devoidfeast    schedule 30.12.2010
comment
@Programming_Kills Защо не спомена тази важна подробност във въпроса? Вижте това.   -  person moinudin    schedule 30.12.2010
comment
Написах урок за това как да внедря алгоритъма на prim в c++, можете да го проверите, може би това ще помогне: 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