3.2. High-Level Version of Prim's Algorithm

Try these first

1. 1.

   What is Prim's Algorithm used for?

   Hint

   Think about trees and cost.

2. 2.

   What does a spanning tree do?

   Hint

   Consider the definition of a tree.

3. 3.

   What does Prim's Algorithm aim to find?

   • Shortest path
   • Minimum cost spanning tree
   • All possible paths

   Hint

   Focus on the word 'cost' in the context of trees.

4. 4.

   True or False: Prim's Algorithm can work on disconnected graphs.

   • True
   • False

   Hint

   Think about the conditions for forming a tree.

5. 5.

   Design a graph with a minimum spanning tree where Prim’s Algorithm would yield different results based on the starting vertex.

   Hint

   Think about symmetry in weigh placements.

6. 6.

   Provide an example where Prim's Algorithm fails to maintain an optimal path if edges are not unique weights.

   Hint

   Consider how you'd approach edge selection in such a situation.