This is how Prim's algorithm runs on our simple test graph:
- It chooses a starting node – node A in the following diagram.
- Iteration 1: It checks all edges connected to that node, and chooses the one with the lowest weight. Vertex B is selected and the edge between A and B is added to the tree.
- Starting from B, it visits C. Among C and D are already visited nodes. The one with the lowest weight is C, so C is selected and the edge between B and C is added to the tree.
- Starting from C, it can go to A, D, and E. A was already visited and the new edge (C->A) would add a higher weight than the already existing one, so this edge is skipped. However, you can see that the new edge reaching D (C->D) has a lower weight than the previously selected edge (A->D), meaning the previous edge is dropped from the tree and the new one is added.
- The last step consists of checking the last node, E. Here, adding the edge between D and E would increase the total...
