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

### Alin Pisica twitter logo github logo Dec 14 '17・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?

DISCUSS (7)

[deleted]

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.

1. A subset of vertices, let's call it V'
2. A subset of edges E', that makes up a (minimal) tree that spans V'
3. A priority queue that:
1. contains all edges on the boundary of V' , i.e. that have one vertex in, and one vertex outside of V' (let's call them type 1 vertex)
2. some edges that are inside of 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 2s and add the first type 1 edge to your spanning tree E', and the new vertex v to V'.

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!

Classic DEV Post from Feb 14

## Which Techie Are You?

Full Stack developer @Equilobe

dev.to now has dark theme. 🌝

Go to the "misc" section of your settings and select night theme

P.S. It's the best move you can make for your dev career.