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