Forskellen mellem Kruskal og Prim
Share
Kruskal vs Prim
Inden for datalogi er Prim's og Kruskals algoritmer en grådig algoritme, der finder et mindst spændende træ for en tilsluttet vægtet, underrettet graf. Et spændende træ er et underbillede af en graf, således at hver knude på grafen er forbundet med en sti, som er et træ. Hvert spændende træ har en vægt, og den mindst mulige vægt / pris for alle spændende træer er det mindste spændende træ (MST).
Mere om Prim's algoritme
Algoritmen blev udviklet af den tjekkiske matematiker Vojtěch Jarník i 1930 og senere uafhængigt af computerforsker Robert C. Prim i 1957. Den blev genopdaget af Edsger Dijkstra i 1959. Algoritmen kan angives i tre nøgletrin;
Givet den tilsluttede graf med n knudepunkter og den respektive vægt på hver kant,
1. Vælg en vilkårlig knude fra grafen og tilføj den til træet T (som vil være den første knude)
2. Overvej vægtene på hver kant, der er forbundet til knudepunkterne i træet, og vælg minimum. Tilføj kanten og noden i den anden ende af træet T, og fjern kanten fra grafen. (Vælg et hvilket som helst, hvis der findes to eller flere minimums)
3. Gentag trin 2, indtil n-1 kanter er føjet til træet.
I denne metode starter træet med en enkelt vilkårlig knude og udvides fra denne knude og frem med hver cyklus. For at algoritmen skal fungere korrekt, skal grafen derfor være en tilsluttet graf. Den grundlæggende form for Prim's algoritme har en tidskompleksitet på O (V2).
Mere om Kruskals algoritme
Algoritmen, der er udviklet af Joseph Kruskal, optrådte i sagen i American Mathematical Society i 1956. Kruskals algoritme kan også udtrykkes i tre enkle trin.
Givet grafen med n knudepunkter og den respektive vægt på hver kant,
1. Vælg lysbuen med mindst vægten af hele grafen, og tilføj til træet og slet fra grafen.
2. Af de resterende skal du vælge den mindst vægtede kant på en måde, der ikke danner en cyklus. Føj kanten til træet og slet fra grafen. (Vælg et hvilket som helst, hvis der findes to eller flere minimums)
3. Gentag processen i trin 2.
I denne metode starter algoritmen med mindst vejet kant og fortsætter med at vælge hver kant ved hver cyklus. I algoritmen behøver grafen derfor ikke at være forbundet. Kruskals algoritme har en tidskompleksitet på O (logV)
Hvad er forskellen mellem Kruskals og Prim's algoritme?
• Prims algoritme initialiseres med en knude, mens Kruskals algoritme starter med en kant.
• Prims algoritmer spænder fra en knude til en anden, mens Kruskals algoritme vælger kanterne på en måde, hvor kantens placering ikke er baseret på det sidste trin.
• I prim's algoritme skal graf være en tilsluttet graf, mens Kruskal'erne også kan fungere på frakoblede grafer.
• Prims algoritme har en tidskompleksitet på O (V2), og Kruskals tidskompleksitet er O (logV).
