loading...

Explain me Prim's Algorithm like I'm five

twitter logo github logo ・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?

twitter logo DISCUSS (7)
markdown guide
 
 

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'.
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!

Classic DEV Post from Feb 14

Which Techie Are You?

Our desks tell a lot about ourselves, don't they? What is your style?

Alin Pisica profile image
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.