# Explain me Prim's Algorithm like I'm five

### Alin Pisica ・1 min read

I can understand much more complex algorithms than this one(Dijkstra, KMP, Karp, etc), but I can't, just can't get around with it. Anywhere I search, I just can't. I understand how it works, but on the implementation I'm zero. What should I do?

Classic DEV Post from Feb 14

I believe the OP was talking about this algorithm: en.wikipedia.org/wiki/Prim%27s_alg...

hahahahahaha.

sorry. and thanks.

Which version do you want to implement? The naive one or the one that uses a priority queue? And where exactly do you struggle? I think you're already beyond the point where a high level explanation would help, if you understand how it works.

Using a priority queue. The naive one, with matrix of costs is kind of intuitive in implementation, or that's how I find it

I think you can reason with a loop invariant. Before any iteration, you have the following 3 variables.

`V'`

`E'`

, that makes up a (minimal) tree that spans`V'`

`V'`

, i.e. that have one vertex in, and one vertex outside of`V'`

(let's call them`type 1`

vertex)`V'`

(let's call them`type 2`

vertex)In your Iteration, you want to add the lowest

`type 1`

vertex to your tree. So you take out edges from your priority queue, discard any`type 2`

s and add the first`type 1`

edge to your spanning tree`E'`

, and the new vertex`v`

to`V'`

.Because your set just got larger, your boundary changed, so you add all edges that are adjacent to your new vertex to the queue.

You now have restored the conditions of your loop invariant, so you can just repeat this step until

`V'`

contains al vertices.To create the invariant initially, you can just take a random vertex

`v`

, the empty set and all edges adjacent to`v`

.Is this of any help?

Yes, it really is. Thank you very, very, much!