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