Kruskal vs Prim
I datavitenskap er Prims og Kruskals algoritmer en grådig algoritme som finner et minimumspennende tre for en tilkoblet vektet, ikke-rettet graf. Et spennende tre er et underbilde av en graf slik at hver node i grafen er forbundet med en bane, som er et tre. Hvert spennende tre har en vekt, og minimum mulige vekter / kostnad for alle de spennende trærne er det minste spennende treet (MST).
Mer om Prims algoritme
Algoritmen ble utviklet av den tsjekkiske matematikeren Vojtěch Jarník i 1930 og senere uavhengig av informatikeren Robert C. Prim i 1957. Den ble gjenoppdaget av Edsger Dijkstra i 1959. Algoritmen kan angis i tre viktige trinn;
Gitt den tilkoblede grafen med noder og respektive vekt på hver kant, 1. Velg en vilkårlig node fra grafen og legg den til treet T (som vil være den første noden)
2. Vurder vektene til hver kant som er koblet til nodene i treet, og velg minimum. Legg til kanten og noden i den andre enden av treet T og fjern kanten fra grafen. (Velg noen hvis to eller flere minimum eksisterer)
3. Gjenta trinn 2 til n-1 kanter er lagt til treet.
I denne metoden starter treet med en enkelt vilkårlig node og utvides fra den noden og utover med hver syklus. Derfor, for at algoritmen skal fungere skikkelig, må grafen være en koblet graf. Den grunnleggende formen til Prims algoritme har en tidskompleksitet på O (V 2).
Mer om Kruskals algoritme
Algoritmen utviklet av Joseph Kruskal dukket opp i saksbehandlingen til American Mathematical Society i 1956. Kruskals algoritme kan også uttrykkes i tre enkle trinn.
Gitt grafen med noder og respektive vekt på hver kant, 1. Velg buen med minst vekt på hele grafen, og legg til i treet og slett det fra grafen.
2. Av de gjenværende velger du den minst vektede kanten, på en måte som ikke danner en syklus. Legg kanten til treet og slett fra grafen. (Velg noen hvis to eller flere minimum eksisterer)
3. Gjenta prosessen i trinn 2.
I denne metoden starter algoritmen med minst vektet kant og fortsetter å velge hver kant i hver syklus. Derfor, i algoritmen, trenger ikke grafen å være koblet sammen. Kruskals algoritme har en tidskompleksitet på O (logV)
Hva er forskjellen mellom Kruskals og Prims algoritme?
• Prims algoritme initialiseres med en node, mens Kruskals algoritme starter med en kant.
• Prims algoritmer spenner fra en node til en annen mens Kruskals algoritme velger kantene på en måte slik at kanten ikke er basert på det siste trinnet.
• I prims algoritme må grafen være en tilkoblet graf mens Kruskals også kan fungere på frakoblede grafer.
• Prims algoritme har en tidskompleksitet på O (V 2), og Kruskals tidskompleksitet er O (logV).
