Skillnad mellan Kruskal och Prim

Kruskal vs Prim

I datavetenskap är Prims och Kruskals algoritmer en girig algoritm som finner ett minsta spannträd för en kopplad vägd, oriktad graf. Ett spannande träd är en delgraf av ett diagram så att varje nod av grafen är ansluten med en bana, som är ett träd. Varje spannande träd har en vikt och de minsta möjliga vikterna / kostnaden för alla spannande träd är det minsta spannande trädet (MST).

Mer om Prims algoritm

Algoritmen utvecklades av tjeckisk matematiker Vojtěch Jarník 1930 och senare oberoende av datavetenskapare Robert C. Prim 1957. Det upptäcktes av Edsger Dijkstra 1959. Algoritmen kan anges i tre nyckelsteg;

Med tanke på det anslutna diagrammet 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å vikterna på varje kant som är kopplade till noderna i trädet och välj minimum. Lägg kanten och noden i den andra änden av trädet T och ta bort kanten från grafen. (Välj något om två eller flera minimum finns)

3. Upprepa steg 2 tills n-1 kanter läggs till trädet.

I denna metod börjar trädet med en enda godtycklig nod och expanderar från den noden framåt med varje cykel. För att algoritmen ska fungera korrekt måste grafen därför vara en kopplad graf. Grundformen för Prims algoritm har en tidskomplexitet av O (V²).

Mer om Kruskals algoritm

Den algoritm som utvecklats av Joseph Kruskal framträdde i det amerikanska matematiska samhällets arbete 1956. Kruskals algoritm kan också uttryckas i tre enkla steg.

Med grafen med n noder och respektive vikt på varje kant,

1. Välj bågen med den minsta vikten av hela grafen och lägg till till trädet och radera från grafen.

2. Av de övriga väljer du den minst viktade kanten, på ett sätt som inte bildar en cykel. Lägg kanten till trädet och radera från grafen. (Välj något om två eller flera minimum finns)

3. Upprepa processen i steg 2.

I denna metod börjar algoritmen med minst viktad kant och fortsätter att välja varje kant vid varje cykel. Därför behöver inte grafen anslutas i algoritmen. Kruskals algoritm har en tidskomplexitet av O (logV)

Vad är skillnaden mellan Kruskals och Prims algoritm?

• Prims algoritm initierar med en nod, medan Kruskals algoritm initierar med en kant.

• Prims algoritmer sträcker sig från en nod till en annan medan Kruskals algoritm väljer kanterna så att kantens position inte är baserad på det sista steget.

• I prims algoritm måste graf vara ett anslutet diagram medan Kruskals kan fungera på bortkopplade grafer också.

• Prims algoritm har en tidskomplexitet av O (V²) och Kruskals tidskomplexitet är O (logV).