Kruskal vs Prim
Në shkencat kompjuterike, algoritmet Prim dhe Kruskal janë një algoritëm i pangopur që gjen një pemë minimale të shtrirjes për një graf të lidhur me peshë të padrejtuar. Një pemë e shtrirë është një nëngraf i një grafi i tillë që çdo nyje e grafikut është e lidhur nga një shteg, i cili është një pemë. Çdo pemë që shtrihet ka një peshë dhe peshat/kostoja minimale e mundshme e të gjitha pemëve që shtrihen është pema me shtrirje minimale (MST).
Më shumë rreth Algoritmit të Prim
Algoritmi u zhvillua nga matematikani çek Vojtěch Jarník në vitin 1930 dhe më vonë në mënyrë të pavarur nga shkencëtari kompjuterik Robert C. Prim në 1957. Ai u rizbulua nga Edsger Dijkstra në 1959. Algoritmi mund të deklarohet në tre hapa kyç;
Duke pasur parasysh grafikun e lidhur me n nyje dhe peshën përkatëse të çdo skaji, 1. Zgjidhni një nyje arbitrare nga grafiku dhe shtojeni në pemën T (e cila do të jetë nyja e parë)
2. Merrni parasysh peshat e secilës skaj të lidhur me nyjet në pemë dhe zgjidhni minimumin. Shtoni skajin dhe nyjen në skajin tjetër të pemës T dhe hiqni skajin nga grafiku. (Zgjidh ndonjë nëse ekzistojnë dy ose më shumë minimume)
3. Përsëriteni hapin 2, derisa n-1 skaj të shtohen në pemë.
Në këtë metodë, pema fillon me një nyje të vetme arbitrare dhe zgjerohet nga ajo nyje e tutje me çdo cikël. Prandaj, që algoritmi të funksionojë siç duhet, grafiku duhet të jetë një grafik i lidhur. Forma bazë e algoritmit të Prim-it ka një kompleksitet kohor prej O(V2).
Më shumë rreth Algoritmit të Kruskal
Algoritmi i zhvilluar nga Joseph Kruskal u shfaq në punimet e Shoqatës Matematikore Amerikane në vitin 1956. Algoritmi i Kruskal mund të shprehet gjithashtu në tre hapa të thjeshtë.
Duke pasur parasysh grafikun me n nyje dhe peshën përkatëse të çdo skaji, 1. Zgjidhni harkun me peshën më të vogël të të gjithë grafikut dhe shtoni në pemë dhe fshini nga grafiku.
2. Nga pjesa e mbetur zgjidhni skajin më pak të peshuar, në një mënyrë që të mos formojë një cikël. Shtoni skajin në pemë dhe fshijeni nga grafiku. (Zgjidh ndonjë nëse ekzistojnë dy ose më shumë minimume)
3. Përsëriteni procesin në hapin 2.
Në këtë metodë, algoritmi fillon me skajin më pak të peshuar dhe vazhdon të zgjedhë secilën skaj në çdo cikël. Prandaj, në algoritëm grafiku nuk ka nevojë të lidhet. Algoritmi i Kruskal ka një kompleksitet kohor prej O(logV)
Cili është ndryshimi midis Algoritmit të Kruskal dhe Prim?
• Algoritmi i Prim inicializohet me një nyje, ndërsa algoritmi i Kruskal fillon me një skaj.
• Algoritmet e Prim shtrihen nga një nyje në tjetrën ndërsa algoritmi i Kruskal zgjedh skajet në një mënyrë që pozicioni i skajit të mos bazohet në hapin e fundit.
• Në algoritmin e prim-it, grafiku duhet të jetë një graf i lidhur ndërsa ai i Kruskal-it mund të funksionojë edhe në grafikë të shkëputur.
• Algoritmi i Prim ka një kompleksitet kohor prej O(V2), dhe kompleksiteti kohor i Kruskal është O(logV).
