Kruskal vs Prim
Inom datavetenskap är Prims och Kruskals algoritmer en girig algoritm som hittar ett minsta spännträd för en sammankopplad vägd oriktad graf. Ett spännträd är en subgraf i en graf så att varje nod i grafen är sammankopplad med en bana, som är ett träd. Varje spännträd har en vikt, och minsta möjliga vikt/kostnad för alla spännträd är minsta spännträd (MST).
Mer om Prims algoritm
Algorithmen utvecklades av den tjeckiske matematikern Vojtěch Jarník 1930 och senare oberoende av datavetaren Robert C. Prim 1957. Den återupptäcktes av Edsger Dijkstra 1959. Algoritmen kan anges i tre nyckelsteg;
Med tanke på den anslutna grafen med n noder och respektive vikt av varje kant, 1. Välj en godtycklig nod från grafen och lägg till den i trädet T (som blir den första noden)
2. Tänk på vikten för varje kant som är ansluten till noderna i trädet och välj minimum. Lägg till kanten och noden i andra änden av trädet T och ta bort kanten från grafen. (Välj något om två eller fler minimikrav finns)
3. Upprepa steg 2 tills n-1 kanter har lagts till i trädet.
I den här metoden börjar trädet med en enda godtycklig nod och expanderar från den noden och framåt med varje cykel. Därför måste grafen vara en sammankopplad graf för att algoritmen ska fungera korrekt. Den grundläggande formen av Prims algoritm har en tidskomplexitet på O(V2).
Mer om Kruskals algoritm
Algorithmen som utvecklats av Joseph Kruskal dök upp i undersökningarna av American Mathematical Society 1956. Kruskals algoritm kan också uttryckas i tre enkla steg.
Med tanke på grafen med n noder och respektive vikt av varje kant, 1. Välj den båge som har minst vikt av hela grafen och lägg till i trädet och ta bort från grafen.
2. Av de återstående välj den minst viktade kanten, på ett sätt som inte bildar en cykel. Lägg till kanten på trädet och ta bort från grafen. (Välj något om två eller fler minimikrav finns)
3. Upprepa processen i steg 2.
I den här metoden börjar algoritmen med minst viktade kant och fortsätter att välja varje kant vid varje cykel. Därför behöver inte grafen vara kopplad i algoritmen. Kruskals algoritm har en tidskomplexitet på O(logV)
Vad är skillnaden mellan Kruskals och Prims algoritm?
• Prims algoritm initieras med en nod, medan Kruskals algoritm initieras med en kant.
• Prims algoritmer spänner från en nod till en annan medan Kruskals algoritm väljer kanterna på ett sätt så att kantens position inte baseras på det sista steget.
• I prims algoritm måste grafen vara en sammankopplad graf medan Kruskals kan fungera även på frånkopplade grafer.
• Prims algoritm har en tidskomplexitet på O(V2), och Kruskals tidskomplexitet är O(logV).
