2.5.1. Prim's Algorithm

Try these first

1. 1.

   Define a spanning tree.

   Hint

   Think about what makes a tree in graph theory.

2. 2.

   What does the term 'acyclic' mean?

   Hint

   Consider the meaning of the prefix 'a-' added to 'cyclic'.

3. 3.

   What is the goal of Prim's Algorithm?

   • To find the shortest path
   • To find a minimum cost spanning tree
   • To find all cycles in a graph

   Hint

   Reflect on the definition of a spanning tree.

4. 4.

   True or False: A spanning tree can have cycles.

   • True
   • False

   Hint

   Remember the acyclic property of trees.

5. 5.

   Consider the following graph with vertices A, B, C, D, and edges connecting them with weights. Apply Prim's Algorithm to find the Minimum Cost Spanning Tree and illustrate the choices made at each step.

   Hint

   Keep track of the already connected vertices to avoid cycles.

6. 6.

   If you have a densely connected graph where many edges have the same minimum weight, how does this affect Prim's Algorithm?

   Hint

   Consider how the algorithm's flexibility can still maintain the properties of a minimum spanning tree.