Search code examples
algorithmgraphgraph-theoryminimum-spanning-treeprims-algorithm

Getting stuck and running out of nodes in Prim's algorithm?

So I have this graph

enter image description here

and I'm trying to build its minimum spanning tree. Starting at vertex A I go A-B-F-E-D and after that there's no place to go, considering that all the adjacent vertexes to D are already part of the tree, how do I keep going?

Also how do I calculate the range of values of a new edge to be part of the minimum spanning tree?

Thanks in advance guys.

Solution

  • I think that you have a slight misunderstanding of how Prim's algorithm works. Based on the description that you gave above, it looks like you think Prim's algorithm works like this:

    • Start at any node.
    • Look at all the nodes connected to the current node that you haven't already visited.
    • Go to the cheapest of these nodes.
    • Repeat until all nodes are covered.

    This is close to how Prim's algorithm works, but it's not exactly right. In Prim's algorithm, there's no notion of a "current" node. Instead, you have two sets of nodes: nodes you've added in, and nodes you haven't. Prim's algorithm then works like this:

    • Start at any node. Add it to the "in" set.
    • Look at all the nodes connected to the "in" set that haven't already been added to the "in" set.
    • Add the cheapest of these nodes to the "in" set.
    • Repeat until all nodes are in the "in" set.

    In the graph that you gave above, you started at node A. Following the algorithm, we look at all nodes connected to A and take the cheapest (B) and add it to the "in" set. The "in" set now contains A and B.

    Now, we look at all the nodes connected to anything in the "in" set. Those are the nodes D, F, E, and H. Of those, the cheapest is H, so we add H to our "in" set, which is now A, B, and H.

    We again look at all the nodes connected to anything in the "in" set. Those are the nodes D, F, E, I, and G. The cheapest of these is F, so we add that in.

    If you repeat this process until all nodes are added, and you keep track of which edges you added in the course of doing so, you'll end up with a minimum spanning tree for the overall graph.

    Hope this helps!