Kruskal vs Prim
Inom datavetenskap är Prims och Kruskals algoritmer en girig algoritm som hittar ett minimalt spännande träd för en ansluten viktad, icke-riktad graf. Ett spännande träd är ett subgraf av ett diagram så att varje nod i diagrammet är ansluten med en bana, vilket är ett träd. Varje spännande träd har en vikt och den minsta möjliga vikten / kostnaden för alla spännande träd är det minsta spännande trädet (MST).
Mer om Prims algoritm
Algoritmen utvecklades av den tjeckiska matematikern Vojtěch Jarník 1930 och senare oberoende av datavetenskaparen Robert C. Prim 1957. Den återupptäcktes av Edsger Dijkstra 1959. Algoritmen kan anges i tre viktiga steg;
Med tanke på det anslutna diagrammet med noder och respektive vikt för varje kant, 1. Välj en godtycklig nod från diagrammet och lägg till den i trädet T (som blir den första noden)
2. Tänk på vikterna för varje kant som är ansluten till noder i trädet och välj lägsta. Lägg till kanten och noden i den andra änden av trädet T och ta bort kanten från diagrammet. (Välj något om det finns två eller flera minimum)
3. Upprepa steg 2 tills n-1-kanter läggs till 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. För att algoritmen ska fungera korrekt måste därför grafen vara en ansluten graf. Grundformen för Prims algoritm har en tidskomplexitet av O (V 2).
Mer om Kruskals algoritm
Algoritmen som utvecklats av Joseph Kruskal uppträdde i American Mathematical Society 1956. Kruskals algoritm kan också uttryckas i tre enkla steg.
Med tanke på diagrammet med noder och respektive vikt för varje kant, 1. Välj bågen med minst vikten för hela grafen och lägg till trädet och ta bort från diagrammet.
2. Av de återstående väljer du den minst viktade kanten, på ett sätt som inte bildar en cykel. Lägg till kanten i trädet och ta bort från diagrammet. (Välj något om det finns två eller flera minimum)
3. Upprepa processen i steg 2.
I den här metoden börjar algoritmen med minst viktad kant och fortsätter att välja varje kant vid varje cykel. Därför behöver grafen inte kopplas i algoritmen. Kruskals algoritm har en tidskomplexitet av 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 sträcker sig 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 ansluten graf medan Kruskals också kan fungera på frånkopplade grafer.
• Prims algoritm har en tidskomplexitet av O (V 2) och Kruskals tidskomplexitet är O (logV).
