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

2024 Автор: Mildred Bawerman | [email protected]. Последнее изменение: 2023-12-16 08:42

Краскал vs Прим

В информатике алгоритмы Прима и Крускала - это жадный алгоритм, который находит минимальное остовное дерево для связного взвешенного неориентированного графа. Остовное дерево - это подграф графа, в котором каждый узел графа соединен путем, который является деревом. Каждое остовное дерево имеет вес, и минимально возможные веса / стоимость всех остовных деревьев - это минимальное остовное дерево (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).