Kruskal vs Prim
I informatikk er Prims og Kruskals algoritmer en grådig algoritme som finner et minimumsspenningstre for en tilkoblet vektet urettet graf. Et spenningstre er en undergraf til en graf slik at hver node i grafen er forbundet med en bane, som er et tre. Hvert spenntre har en vekt, og den minste mulige vekten/kostnaden for alle spenntrærne er minimumsspenningstreet (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 nøkkeltrinn;
Gitt den tilkoblede grafen med n noder og respektive vekt av 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 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 en hvis to eller flere minimumskrav finnes)
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 riktig, må grafen være en tilkoblet graf. Den grunnleggende formen for Prims algoritme har en tidskompleksitet på O(V2).
Mer om Kruskals algoritme
Algorithmen utviklet av Joseph Kruskal dukket opp i forhandlingene til American Mathematical Society i 1956. Kruskals algoritme kan også uttrykkes i tre enkle trinn.
Gitt grafen med n noder og respektive vekt av hver kant, 1. Velg buen med minst vekt av hele grafen og legg til i treet og slett fra grafen.
2. Av de resterende velg den minst vektede kanten, på en måte som ikke danner en syklus. Legg til kanten på treet og slett fra grafen. (Velg en hvis to eller flere minimumskrav finnes)
3. Gjenta prosessen i trinn 2.
I denne metoden starter algoritmen med minst vektet kant og fortsetter å velge hver kant ved hver syklus. Derfor trenger ikke grafen å være koblet i algoritmen. 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 edge.
• Prims algoritmer spenner fra en node til en annen mens Kruskals algoritme velger kantene på en måte som gjør at posisjonen til kanten ikke er basert på det siste trinnet.
• I prims algoritme må grafen være en tilkoblet graf, mens Kruskal-ene også kan fungere på frakoblede grafer.
• Prims algoritme har en tidskompleksitet på O(V2), og Kruskals tidskompleksitet er O(logV).
