4.2. Complexity Analysis

Try these first

1. 1.

   Define Prim's Algorithm.

   Hint

   Think about how it chooses edges.

2. 2.

   What is the time complexity with an adjacency matrix?

   Hint

   What happens when you check each vertex?

3. 3.

   What does Prim's algorithm aim to achieve?

   • Find the shortest path
   • Generate a minimum spanning tree
   • Sort edges in a graph

   Hint

   What kind of tree connects all vertices with minimal total weight?

4. 4.

   True or False: Dijkstra's and Prim's algorithms can be used interchangeably.

   • True
   • False

   Hint

   Consider their main goals.

5. 5.

   Given a connected graph, can you demonstrate how Prim’s algorithm would differ if edge weights were not unique?

   Hint

   Think about scenarios with equal weight edges.

6. 6.

   How can you optimize Prim’s algorithm for a sparse graph?

   Hint

   Which graph representation reduces checking time?