Question

Implement Prim’s algorithm on your system. Process the result step by step and study the

performance of the algorithm on different graphs.

Answer 1

Prim’s algorithm:

1. Select a random vertex.
2. Choose the path with the minimum weight connected to the chosen vertex.
3. The path will lead you to a new vertex, position yourself there.
4. Once you have formed/updated the initial tree, choose the path with the minimum weight that is connected to the whole tree. You must avoid creating cycles.
5. Repeat the steps 3 and 4 until you have covered all the vertices.