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

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

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

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

Алгоритъмът е разработен от чешкия математик Войтех Ярник през 1930 г. и по-късно независимо от компютърния специалист Робърт К. Прим през 1957 г. Той е преоткрит от Едсгер Дийкстра през 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²), а времевата сложност на Крускал е O (logV).