Prim's Algorithm

Explanation

- **Prim’s Algorithm** is a greedy algorithm used to find the **minimum spanning tree (MST)** of a graph. It builds the MST by starting from an arbitrary node and adding the smallest edge connecting a vertex in the MST to a vertex outside it.

-

• Steps:

  • Start from an arbitrary vertex and mark it as part of the MST.
  • Select the smallest edge connecting the MST to a vertex outside the MST and add it to the MST.
  • Repeat until all vertices are included in the MST.

• Time Complexity:

  • O(E log V), where V is the number of vertices and E is the number of edges (using priority queue)