3. Spanning Trees: Prim’s Algorithm

Try these first

1. 1.

   What is a spanning tree?

   Hint

   Think of a tree structure that includes all vertices.

2. 2.

   What does Prim's algorithm aim to find?

   Hint

   Consider what 'minimum cost' means in relation to edge weights.

3. 3.

   What is the purpose of Prim's algorithm?

   • Find the minimum spanning tree
   • Sort the graph
   • Cycle detection

   Hint

   Consider what the term 'minimizing cost' relates to.

4. 4.

   Does Prim's algorithm always produce the optimal spanning tree?

   • True
   • False

   Hint

   Recall the purpose of the algorithm.

5. 5.

   Suppose you have a graph with vertices A, B, C, and D and edges with weights as follows: AB(1), AC(4), AD(3), BC(2), BD(5), CD(2). Walk through Prim's algorithm step-by-step to find the minimum spanning tree.

   Hint

   How do you choose the next edge after the first?

6. 6.

   Consider a scenario where multiple edges have the same weight in your graph. Discuss potential adjustments needed for Prim's algorithm to maintain optimal results.

   Hint

   How does ambiguity in edge weights affect decision making?