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.
I think you can reason with a loop invariant. Before any iteration, you have the following 3 variables.
A subset of vertices, let's call it V'
A subset of edges E', that makes up a (minimal) tree that spans V'
A priority queue that:
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)
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.
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 spansV'V', i.e. that have one vertex in, and one vertex outside ofV'(let's call themtype 1vertex)V'(let's call themtype 2vertex)In your Iteration, you want to add the lowest
type 1vertex to your tree. So you take out edges from your priority queue, discard anytype 2s and add the firsttype 1edge to your spanning treeE', and the new vertexvtoV'.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 tov.Is this of any help?
Yes, it really is. Thank you very, very, much!