Разница между Крускалом и Примом

Крускал против Прим

В информатике алгоритмы Прима и Крускала являются жадным алгоритмом, который находит минимальное остовное дерево для связанного взвешенного неориентированного графа. Покрывающее дерево - это подграф графа, такой, что каждый узел графа связан путем, который является деревом. Каждое связующее дерево имеет вес, а минимально возможный вес / стоимость всех связующих деревьев - это минимальное остовное дерево (MST).

Подробнее об алгоритме Прима

Алгоритм был разработан чешским математиком Войтехом Ярником в 1930 году, а позже независимым ученым-программистом Робертом С. Примом в 1957 году. Он был заново открыт Эдсгером Дейкстрой в 1959 году. Алгоритм можно сформулировать в три ключевых этапа;

Дан связанный граф с n узлами и соответствующим весом каждого ребра,

1. Выберите произвольный узел на графике и добавьте его в дерево T (которое будет первым узлом).

2. Рассмотрите веса каждого ребра, соединенного с узлами в дереве, и выберите минимум. Добавьте ребро и узел на другом конце дерева T и удалите ребро из графика. (Выберите любой, если существует два или более минимума)

3. Повторяйте шаг 2, пока в дерево не будут добавлены n-1 ребра.

В этом методе дерево начинается с одного произвольного узла и расширяется от этого узла с каждым циклом. Следовательно, для правильной работы алгоритма граф должен быть связным графом. Базовая форма алгоритма Прима имеет временную сложность O (V²).

Подробнее об алгоритме Крускала

Алгоритм, разработанный Джозефом Крускалом, появился в трудах Американского математического общества в 1956 году. Алгоритм Крускала также можно выразить в три простых шага..

Дан график с n узлами и соответствующим весом каждого ребра,

1. Выберите дугу с наименьшим весом всего графика, добавьте в дерево и удалите из графика..

2. Из оставшихся выберите наименее взвешенное ребро таким образом, чтобы не образовывать цикл. Добавьте ребро к дереву и удалите из графика. (Выберите любой, если существует два или более минимума)

3. Повторите процесс в шаге 2.

В этом методе алгоритм начинается с наименее взвешенного ребра и продолжает выбирать каждое ребро в каждом цикле. Следовательно, в алгоритме граф не нужно связывать. Алгоритм Крускала имеет временную сложность O (logV)

В чем разница между алгоритмом Крускала и Прима?

• Алгоритм Прима инициализируется узлом, а алгоритм Крускала - ребром.

• Алгоритмы Прима распространяются от одного узла к другому, в то время как алгоритм Крускала выбирает ребра таким образом, что положение ребра не основано на последнем шаге..

• В алгоритме Прима граф должен быть связным графом, в то время как Крускал может функционировать и на несвязных графах..

• Алгоритм Прима имеет временную сложность O (V²), а временная сложность Крускала равна O (logV).