Prim's algorithm is a greedy algorithm that is used to find the minimum spanning tree (MST) for a connected weighted undirected graph. The MST is a subset of the edges that connects all vertices together, without any cycles and with the minimum possible total edge weight.

Key Points

  • Greedy Approach: Prim's algorithm follows a greedy approach where at each step it chooses the next edge with the minimum weight that connects a vertex in the MST to a vertex not yet in the MST.
  • Steps:
    1. Start with any vertex.
    2. Add the minimum weight edge that connects the MST to a vertex not in the MST.
    3. Repeat step 2 until all vertices are in the MST.
  • Applications: Used in network design, map overlay, and other fields.

Algorithm Steps

  1. Create a set of all the vertices in the graph.
  2. Initialize the MST as a set containing the starting vertex.
  3. Set the initial minimum weight edge to null.
  4. While the MST does not contain all the vertices:
    • For each vertex in the MST, find all its adjacent vertices and their corresponding edge weights.
    • Choose the edge with the minimum weight that connects a vertex in the MST to a vertex not yet in the MST.
    • Add the vertex not in the MST to the MST.
    • Update the minimum weight edge if a smaller weight edge is found.

Example

Here's a simple example of Prim's algorithm applied to a graph:

- A: {B (10), C (6)}
- B: {A (10), C (15), D (5)}
- C: {A (6), B (15), D (9)}
- D: {B (5), C (9)}

Prim's Algorithm Execution:

  1. Start with vertex A.
  2. Choose edge A-C with weight 6.
  3. Now MST contains A and C.
  4. Choose edge C-D with weight 9.
  5. MST now contains A, C, and D.
  6. Choose edge B-D with weight 5.
  7. MST is now complete, containing all vertices A, B, C, and D.

Learn More

To dive deeper into Prim's algorithm, you can check out our Graph Theory Tutorial.

[center]
<img src="https://cloud-image.ullrai.com/q/algorithm_graph/" alt="Algorithm Graph"/>
</center>