19.2.2. Prim’s Algorithm

Try these first

1. 1.

   What does a greedy algorithm do?

   Hint

   Think about local vs. global optimization.

2. 2.

   What is the goal of Prim's Algorithm?

   Hint

   Connect all vertices with the least total edge weight.

3. 3.

   What is the primary goal of Prim's Algorithm?

   • Maximize the edge weights
   • Minimize the edge weights
   • Connect all vertices randomly

   Hint

   Think about what an optimal solution means.

4. 4.

   True or False: Prim's Algorithm can revisit previously made choices.

   • True
   • False

   Hint

   Remember the greedy approach.

5. 5.

   Given a graph with specific vertices and edges, demonstrate the step-by-step use of Prim's Algorithm, showing each choice and the resulting MST.

   Hint

   Remember to always choose the smallest weight edge that connects a new vertex.

6. 6.

   Explain how a change in edge weights affects the outcome of Prim’s Algorithm. Provide an example.

   Hint

   Use different scenarios to stress-test the algorithm's adaptability.