Крускал против Прим
В информатике алгоритмы Прима и Крускала - это жадные алгоритмы, которые находят минимальное остовное дерево для связного взвешенного неориентированного графа. Остовное дерево - это подграф графа, каждый узел которого соединен путем, являющимся деревом. Каждое остовное дерево имеет вес, а минимально возможные веса/стоимость всех остовных деревьев - это минимальное остовное дерево (MST).
Подробнее об алгоритме Прима
Алгоритм был разработан чешским математиком Войтехом Ярником в 1930 году, а затем независимо ученым-компьютерщиком Робертом С. Примом в 1957 году. Он был заново открыт Эдсгером Дейкстрой в 1959 году. Алгоритм можно сформулировать в три ключевых этапа:
Для связного графа с n узлами и соответствующим весом каждого ребра
1. Выберите произвольный узел из графа и добавьте его в дерево T (которое будет первым узлом)
2. Учитывайте веса каждого ребра, соединенного с узлами дерева, и выбирайте минимум. Добавьте ребро и узел на другом конце дерева T и удалите ребро из графа. (Выберите любой, если существует два или более минимума)
3. Повторяйте шаг 2, пока в дерево не будет добавлено n-1 ребер.
В этом методе дерево начинается с одного произвольного узла и расширяется от этого узла с каждым циклом. Следовательно, для правильной работы алгоритма граф должен быть связным графом. Базовая форма алгоритма Прима имеет временную сложность O(V2).
Подробнее об алгоритме Крускала
Алгоритм, разработанный Джозефом Крускалом, появился в трудах Американского математического общества в 1956 году. Алгоритм Крускала также можно выразить тремя простыми шагами.
Для графа с n узлами и соответствующим весом каждого ребра
1. Выбрать дугу с наименьшим весом из всего графа и добавить в дерево и удалить из графа.
2. Из оставшихся выберите наименее взвешенное ребро таким образом, чтобы не образовывался цикл. Добавьте ребро в дерево и удалите из графа. (Выберите любой, если существует два или более минимума)
3. Повторите процесс в шаге 2.
В этом методе алгоритм начинает с наименее взвешенного ребра и продолжает выбирать каждое ребро в каждом цикле. Поэтому в алгоритме граф может не быть связным. Алгоритм Крускала имеет временную сложность O(logV)
В чем разница между алгоритмами Крускала и Прима?
• Алгоритм Прима инициализируется узлом, а алгоритм Крускала - ребром.
• Алгоритмы Прима переходят от одного узла к другому, в то время как алгоритм Крускала выбирает ребра таким образом, что положение ребра не зависит от последнего шага.
• В алгоритме Прима граф должен быть связным графом, в то время как алгоритм Крускала может работать и на несвязных графах.
• Алгоритм Прима имеет временную сложность O(V2), а временная сложность Крускала – O(logV).
