Когда использовать алгоритм Краскала по сравнению с алгоритмом Прима

Возможный дубликат:
Краскал против Прим

Когда бы вы использовали алгоритм Краскала вместо алгоритма Прима, чтобы найти минимальное остовное дерево? Какие входные графы и узлы лучше для каждого типа? В каких случаях использование одного из них более эффективно, когда речь идет о пространстве и времени?

Являются ли их конкретные исходные данные, которые делают одно намного лучше другого?


graph algorithm prims-algorithm kruskals-algorithm
person Georges Krinker    schedule 11.12.2012    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Одно важное отличие: если ваш график отключен, Prim не принесет вам никакой пользы (требуется, чтобы граф был подключен). С другой стороны, Kruskal будет работать на связном или несвязном графе; в последнем случае он находит минимальный остовный лес, MST каждого связного компонента.

person kaveman    schedule 11.12.2012