Опис алгоритма
Као што смо рекли Крускалов алгоритам проналази минимално разапињуће стабло, односно шуму, за тежински граф.
Кораци:
- Сортирају се све ивице графа у неопадајућем редоследу
- Итерирамо кроз ивице графа, уколико додавање ивице у стабло не прави циклус, додамо ивицу
- На крају добијемо минимално разапињућу шуму уколико граф није повезан, односно минимално разапињуће стабло уколико је граф повезан
Слични алгоритми (други алгоритми проналаска минималног разапињућег стабла):
| Алгоритам |
Временска комплексност |
Година открића |
| Борувкин алгоритам |
O(|E|log|V|) |
1926 |
| Примов алгоритам |
O(|E|log|V|) |
1957 |
| Алгоритам обрнутог брисања |
O(E log V (log log V)³) |
1956 |