Algorithms For Dummies

Leveraging Prim’s algorithm

Prim’s algorithm generates the minimum spanning tree for a graph by traversing 

the graph vertex by vertex. Starting from any chosen vertex, the algorithm adds 

edges using a constraint in which, if one vertex is currently part of the spanning 

tree and the second vertex isn’t part of it, the edge weight between the two must be 

the least possible among those available. By proceeding in this fashion, creating 

cycles in the spanning tree is impossible (it could happen only if you add an edge 

whose vertexes are already both in the spanning tree) and you’re guaranteed to 

obtain a minimal tree because you add the edges with the least weight. In terms of 

steps, the algorithm includes these three phases, with the last one being iterative:

1. 

Track both the edges of the minimum spanning tree and the used vertexes as 

they become part of the solution.

---

188

 

   

  PART 3