Разлика между Kruskal и Prim

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

Крускал срещу Прим

В компютърните науки алгоритмите на Prim и Kruskal са алчен алгоритъм, който намира минимално обхващащо дърво за свързана претеглена неориентирана графика. Обхващащото дърво е подграф на графика, така че всеки възел на графиката е свързан с път, който е дърво. Всяко обхващащо дърво има тегло, а минималното възможно тегло / цена на всички обхващащи дървета е минималното обхващащо дърво (MST).

Повече за алгоритъма на Prim

Алгоритъмът е разработен от чешкия математик Войтех Ярник през 1930 г. и по-късно самостоятелно от компютърния учен Робърт К. Прим през 1957 г. Той е преоткрит от Edsger Dijkstra през 1959 г. Алгоритъмът може да бъде посочен в три ключови стъпки;

Като се има предвид свързаната графика с n възли и съответното тегло на всеки ръб, 1. Изберете произволен възел от графиката и го добавете към дървото T (което ще бъде първият възел)

2. Помислете за тежестите на всеки ръб, свързан с възлите в дървото и изберете минималния. Добавете ръба и възела в другия край на дървото T и премахнете ръба от графиката. (Изберете всеки, ако съществуват два или повече минимума)

3. Повторете стъпка 2, докато n-1 ръбовете се добавят към дървото.

При този метод дървото започва с един произволен възел и се разширява от този възел нататък с всеки цикъл. Следователно, за да работи алгоритъмът правилно, графиката трябва да е свързана графика. Основната форма на алгоритъма на Prim има времева сложност на O (V ²).

Повече за алгоритъма на Крускал

Алгоритъмът, разработен от Джоузеф Крускал, се появява в сборника на Американското математическо общество през 1956 г. Алгоритъмът на Крускал също може да бъде изразен в три прости стъпки.

Като се има предвид графиката с n възли и съответното тегло на всеки ръб, 1. Изберете дъгата с най-малко тегло на цялата графика и добавете към дървото и изтрийте от графиката.

2. От останалите изберете най-малко претегления ръб по начин, който не образува цикъл. Добавете ръба към дървото и изтрийте от графиката. (Изберете всеки, ако съществуват два или повече минимума)

3. Повторете процеса в стъпка 2.

При този метод алгоритъмът започва с най-малко претегления ръб и продължава да избира всеки ръб при всеки цикъл. Следователно в алгоритъма не е необходимо графиката да бъде свързана. Алгоритъмът на Крускал има времева сложност на O (logV)

Каква е разликата между алгоритъма на Крускал и Прим?

• Алгоритъмът на Prim се инициализира с възел, докато алгоритъмът на Kruskal инициира с ръб.

• Алгоритмите на Prim се разпростират от един възел на друг, докато алгоритъмът на Kruskal избира ръбовете по начин, при който положението на ръба не се основава на последната стъпка.

• В алгоритъма на prim, графиката трябва да е свързана графика, докато Kruskal може да функционира и на несвързани графики.

• Алгоритъмът на Prim има времева сложност на O (V ²), а времевата сложност на Kruskal е O (logV).