Крускал срещу Прим
В компютърните науки алгоритмите на Prim и Kruskal са алчен алгоритъм, който намира минимално обхващащо дърво за свързан претеглен неориентиран граф. Обхващащото дърво е подграф на граф, така че всеки възел на графиката е свързан с път, който е дърво. Всяко обхващащо дърво има тегло и минималните възможни тегла/цена на всички обхващащи дървета е минималното обхващащо дърво (MST).
Повече за алгоритъма на Prim
Алгоритъмът е разработен от чешкия математик Vojtěch Jarník през 1930 г. и по-късно независимо от компютърния учен Робърт С. Прим през 1957 г. Той е преоткрит от Edsger Dijkstra през 1959 г. Алгоритъмът може да бъде формулиран в три ключови стъпки;
Дадена е свързаната графа с n възли и съответното тегло на всеки ръб, 1. Изберете произволен възел от графиката и го добавете към дървото T (което ще бъде първият възел)
2. Помислете за теглата на всеки ръб, свързан с възлите в дървото, и изберете минимума. Добавете ръба и възела в другия край на дървото T и премахнете ръба от графиката. (Изберете който и да е, ако съществуват два или повече минимума)
3. Повторете стъпка 2, докато към дървото се добавят n-1 ръба.
При този метод дървото започва с един произволен възел и се разширява от този възел нататък с всеки цикъл. Следователно, за да работи алгоритъмът правилно, графиката трябва да бъде свързана графика. Основната форма на алгоритъма на Prim има времева сложност O(V2).
Повече за алгоритъма на Kruskal
Алгоритъмът, разработен от Джоузеф Крускал, се появява в докладите на Американското математическо общество през 1956 г. Алгоритъмът на Крускал може да се изрази и в три прости стъпки.
Дадена е графиката с n възела и съответното тегло на всеки ръб, 1. Изберете дъгата с най-малко тегло от цялата графика и добавете към дървото и изтрийте от графиката.
2. От останалите изберете най-малко претегления ръб, по начин, който не образува цикъл. Добавете ръба към дървото и изтрийте от графиката. (Изберете който и да е, ако съществуват два или повече минимума)
3. Повторете процеса в стъпка 2.
В този метод алгоритъмът започва с най-малко претеглен ръб и продължава да избира всеки ръб при всеки цикъл. Следователно в алгоритъма не е необходимо графиката да бъде свързана. Алгоритъмът на Kruskal има времева сложност от O(logV)
Каква е разликата между алгоритъма на Kruskal и Prim?
• Алгоритъмът на Prim инициализира с възел, докато алгоритъмът на Kruskal инициира с край.
• Алгоритмите на Prim се простират от един възел до друг, докато алгоритъмът на Kruskal избира ръбовете по начин, по който позицията на ръба не се основава на последната стъпка.
• В алгоритъма на Prim графиката трябва да е свързана графа, докато Kruskal може да функционира и върху несвързани графи.
• Алгоритъмът на Prim има времева сложност O(V2), а времевата сложност на Kruskal е O(logV).
