Kruskal vs Prim
I datalogi er Prims og Kruskals algoritmer en grådig algoritme, der finder et minimum spændende træ til en sammenhængende vægtet, ikke-rettet graf. Et spændende træ er et underbillede af en graf, således at hver knude i 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 mindst spændende træ (MST).
Mere om Prims algoritme
Algoritmen blev udviklet af den tjekkiske matematiker Vojtěch Jarník i 1930 og senere uafhængigt af datalog 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-noder og den respektive vægt af hver kant, 1. Vælg en vilkårlig node fra grafen og tilføj den til træet T (som vil være den første node)
2. Overvej vægten af hver kant, der er forbundet med knudepunkterne i træet, og vælg minimumet. Tilføj kanten og noden i den anden ende af træet T, og fjern kanten fra grafen. (Vælg et, hvis der findes to eller flere minimum)
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 node og udvides fra denne node og frem med hver cyklus. For at algoritmen skal fungere korrekt, skal grafen derfor være en tilsluttet graf. Den grundlæggende form for Prims algoritme har en tidskompleksitet på O (V 2).
Mere om Kruskals algoritme
Algoritmen udviklet af Joseph Kruskal dukkede op under proceduren i American Mathematical Society i 1956. Kruskals algoritme kan også udtrykkes i tre enkle trin.
Givet grafen med n-noder og den respektive vægt af hver kant, 1. Vælg buen med den mindste vægt af hele grafen, og tilføj til træet, og slet den 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, hvis der findes to eller flere minimum)
3. Gentag processen i trin 2.
I denne metode starter algoritmen med den mindst vægtede kant og fortsætter med at vælge hver kant ved hver cyklus. Derfor behøver grafen ikke at blive forbundet i algoritmen. Kruskals algoritme har en tidskompleksitet på O (logV)
Hvad er forskellen mellem Kruskals og Prims algoritme?
• Prims algoritme initialiseres med en node, mens Kruskals algoritme starter med en kant.
• Prims algoritmer spænder fra en node til en anden, mens Kruskals algoritme vælger kanterne på en måde, så kantens position ikke er baseret på det sidste trin.
• I prims algoritme skal grafen være en tilsluttet graf, mens Kruskals også kan fungere på frakoblede grafer.
• Prims algoritme har en tidskompleksitet på O (V 2), og Kruskals tidskompleksitet er O (logV).
