Prim’s Algorithm

@prims_algorithm

Prim’s Algorithm builds a Minimum Spanning Tree (MST) by starting from one node and growing the tree step by step, always adding the smallest edge that connects a new node.

Pseudo-code
function prim(graph, start):

  # Step 1: Initialize
  for each vertex v in graph:
    key[v] = INF           # best known edge weight
    parent[v] = null      # to store MST

  key[start] = 0

  # Step 2: Use priority queue
  pq = priority queue of all vertices based on key[]

  MST = empty set

  # Step 3: Build MST
  while pq is not empty:

    u = extract_min(pq)
    MST.add(u)

    # Step 4: Update neighbors
    for each neighbor v of u:
      if v not in MST and weight(u, v) < key[v]:
        key[v] = weight(u, v)
        parent[v] = u
        update pq with new key[v]

  return parent
  • V The set of all vertices (nodes) in the graph.
  • E The set of all edges with weights (costs).
  • G The graph structure containing nodes and weighted edges.
  • INF A very large value representing infinity, used to initialize distances.
Recipe Steps
1

Start from one node — Imagine picking one city to begin building your network.

2

Look at all nearby edges — Find all roads connected to your current tree.

3

Pick the cheapest edge that connects to a new city.

4

Add that city and edge to your growing tree.

5

Repeat until all cities are connected into one network.

Questions & Answers

Grow a tree by always adding the closest new node.

Prim grows from a single starting node, while Kruskal builds from edges globally.

The minimum edge weight needed to connect vertex v to the MST.

The smallest edge connecting the current tree to a new node.
- Time complexity is O(E log V) with a priority queue.
- Works only on connected graphs.
- Tip: Think of it as growing a tree outward step by step.
- Common mistake: Forgetting to update keys when a better edge is found.
- Efficient for dense graphs compared to Kruskal.

Related Algorithms
Dinic's Algorithm

Dinic's Algorithm finds the maximum flow in a network by building layers using BFS and then sending flow using DFS in these layers, making it faster than simpler methods.

View
Kruskal's Algorithm

Kruskal's Algorithm finds a Minimum Spanning Tree (MST) by always picking the smallest edge that does not form a cycle, until all nodes are connected.

View