Різниця між Крускалом та Прим
Share
Крускал проти Прима
В інформатиці алгоритми Прима та Крускала - жадібний алгоритм, який знаходить мінімальне прольотове дерево для підключеного зваженого непрямого графа. Дерево, що охоплює, - це підграф графіка, такий, що кожен вузол графа пов'язаний шляхом, який є деревом. Кожне spanning дерево має вагу, і мінімальна можлива вага / вартість усіх spanning дерев є мінімальною spanning tree (MST).
Більше про алгоритм Прима
Алгоритм був розроблений чеським математиком Войтехом Ярніком в 1930 році, а згодом незалежно комп'ютерним науком Робертом Ч. Примом в 1957 році. Його було відкрито Едсгером Дійкстра в 1959 році.
Дано зв'язаний графік з n вузлами та відповідною вагою кожного краю,
1. Виберіть довільний вузол із графіка та додайте його до дерева T (яке буде першим вузлом)
2. Розгляньте ваги кожного краю, з'єднаного з вузлами на дереві, і виберіть мінімум. Додайте край та вузол на іншому кінці дерева T та видаліть край з графіка. (Виберіть будь-який, якщо існує два або більше мінімумів)
3. Повторіть крок 2, поки n-1 краї не будуть додані до дерева.
У цьому методі дерево починається з одного довільного вузла і розширюється від цього вузла далі з кожним циклом. Отже, щоб алгоритм працював належним чином, графік повинен бути підключеним графіком. Основна форма алгоритму Прима має часову складність O (V2).
Більше про алгоритм Крускала
Алгоритм, розроблений Джозефом Крускалом, з'явився в роботі Американського математичного товариства в 1956 році. Алгоритм Крускала також може бути виражений трьома простими кроками.
Дано графік з n вузлами та відповідною вагою кожного краю,
1. Виберіть дугу з найменшою вагою всього графа та додайте до дерева та видаліть із графіка.
2. З решти виберіть найменш зважений край таким чином, що не утворює циклу. Додайте край до дерева та видаліть із графіка. (Виберіть будь-який, якщо існує два або більше мінімумів)
3. Повторіть процес на кроці 2.
У цьому методі алгоритм починається з найменш зваженого краю і продовжує вибір кожного краю на кожному циклі. Тому в алгоритмі графік не потрібно підключати. Алгоритм Крускала має часову складність O (logV)
Яка різниця між алгоритмом Крускала та Прима?
• Алгоритм Прима ініціалізується вузлом, тоді як алгоритм Крускала ініціює ребром.
• Алгоритми Прама охоплюють один вузол до іншого, тоді як алгоритм Крускала вибирає ребра таким чином, щоб положення ребра не базувалося на останньому кроці.
• В алгоритмі Prim, графік повинен бути пов'язаним графіком, тоді як Kruskal може працювати і на відключених графіках.
• Алгоритм Прима має часову складність O (V2), а часова складність Крускала - O (logV).
