Kruskal vs Prim
Inden for datalogi er Prims og Kruskals algoritmer en grådig algoritme, der finder et minimum spændingstræ for en forbundet vægtet urettet graf. Et spændingstræ er en undergraf til en graf, således at hver knude på grafen er forbundet med en sti, som er et træ. Hvert spændingstræ har en vægt, og den mindst mulige vægt/omkostning for alle spændingstræerne er minimumsspændingstræet (MST).
Mere om Prims algoritme
Algoritmen blev udviklet af den tjekkiske matematiker Vojtěch Jarník i 1930 og senere uafhængigt af datalogen Robert C. Prim i 1957. Den blev genopdaget af Edsger Dijkstra i 1959. Algoritmen kan angives i tre nøgletrin;
Givet den forbundne graf med n noder og 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 noderne i træet, og vælg minimum. Tilføj kanten og knudepunktet i den anden ende af træet T og fjern kanten fra grafen. (Vælg en, hvis der findes to eller flere minimumskrav)
3. Gentag trin 2, indtil n-1 kanter er tilføjet til træet.
I denne metode starter træet med en enkelt vilkårlig node og udvider sig fra den node og fremefter med hver cyklus. Derfor, for at algoritmen skal fungere korrekt, skal grafen være en forbundet graf. Den grundlæggende form for Prims algoritme har en tidskompleksitet på O(V2).
Mere om Kruskals algoritme
Algorithmen udviklet af Joseph Kruskal dukkede op i forhandlingerne fra American Mathematical Society i 1956. Kruskals algoritme kan også udtrykkes i tre enkle trin.
Givet grafen med n noder og respektive vægt af hver kant, 1. Vælg den bue med mindst vægt af hele grafen, og fø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. Tilføj kanten til træet og slet fra grafen. (Vælg en, hvis der findes to eller flere minimumskrav)
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 i algoritmen ikke at være forbundet. Kruskals algoritme har en tidskompleksitet på O(logV)
Hvad er forskellen mellem Kruskals og Prims algoritme?
• Prims algoritme initialiseres med en node, hvorimod Kruskals algoritme starter med en kant.
• Prims algoritmer spænder fra én 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 forbundet graf, mens Kruskal'erne også kan fungere på afbrudte grafer.
• Prims algoritme har en tidskompleksitet på O(V2), og Kruskals tidskompleksitet er O(logV).
