Prim's Algorithm

Overview

Prim's Algorithm is a greedy algorithm used for finding a minimum spanning tree in a weighted, undirected graph. It progressively builds the spanning tree by selecting the cheapest available edge.

Key Steps:

  1. Start with an arbitrary vertex and mark it as part of the spanning tree.
  2. Select the smallest edge connecting a vertex in the tree to a vertex outside the tree.
  3. Add the selected edge and the new vertex to the tree, and repeat until all vertices are included.
Diagram illustrating Prim's Algorithm

For further details, check out the Wikipedia page on Prim's Algorithm.