Prim’s Algorithm: The “Lazy Electrician” Strategy

How to conquer a graph without wasting a single meter of wire.

If you look at a textbook, Prim’s Algorithm is a collection of sets, priority queues, and relaxations. If you look at the real world, Prim’s Algorithm is just a Lazy Electrician trying to save money.

Here is the truth: The reason people forget Prim’s is that they confuse it with Dijkstra’s. They look almost identical in code. But their soul is different.

By the end of this article, you won’t just know Prim’s; you’ll know exactly why it exists.

The Scenario: The Stingy Empire

Forget “nodes” and “edges” for a second.

Imagine you are an Internet Service Provider (ISP). You have just won a contract to provide fiber internet to a new neighborhood with 10 houses.

• The Goal: Every house must be connected to the network.
• The Constraint: Fiber cable is incredibly expensive.
• The Rule: You can’t just drop cables randomly. You have to extend the network from a house that is already connected.

You are a Lazy Electrician. You want to use the absolute minimum amount of wire to get the job done. You don’t care about speed; you care about cost.

The Mechanics: How the “Infection” Spreads

Prim’s algorithm is a Greedy Algorithm. It doesn’t plan ahead. It doesn’t look at the whole map. It only looks at what is right in front of it.

Think of your network as a growing mold or infection. It starts at one spot and oozes outward, always taking the path of least resistance.

The 3-Step Loop

1. Pick a Start: It doesn’t matter where. Pick House A. House A is now “infected” (part of your network).

2. Scan the Frontier: Look at every wire connecting your “infected” houses to the “uninfected” outside world.

3. Be Cheap: Pick the shortest wire you can see. Add that new house to your network.

Repeat until everyone is infected.

A Visual Walkthrough

Let’s run the simulation.

• Step 0: You stand at House A.
• Step 1: You look at the neighbors.
• Path A to B costs $100.
• Path A to C costs $20.
• Step 2: You are cheap. You pick A to C. Now you own House A and House C.
• Step 3 (The Crucial Step): You are now standing at both A and C. You look at all options from your new empire:
• From A to B ($100).
• From C to D ($15).
• From C to E ($50).
• Step 4: $15 is the cheapest. You build C to D. Now you own {A, C, D}.

Notice what just happened: You completely ignored the A to B path because it was expensive. You found a cheaper way to expand your empire through C. The “infection” chose the easiest victim.

The “Blind Spot”: Prim’s vs. Dijkstra

This is where 90% of students fail. They write code for Prim’s, but they accidentally write Dijkstra’s instead.

The Difference is in the “Why”:

• Dijkstra is a GPS. It wants to know the total distance from the starting point. It cares about the cumulative sum (Start $\to$ A $\to$ B $\to$ C).
• Prim is a Connector. It does not care how far away the house is from the start. It only cares about the cost of the single wire needed to connect it to the blob.

The Golden Rule:

In Prim’s, the “score” of a node is just the weight of the edge connecting it to your tree.

In Dijkstra, the “score” is the weight of the edge + distance traveled so far.

How to Code It (Mental Model)

Don’t memorize the Python/C++ syntax. Memorize the Data Structures.

Get Namrata’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To be a “Lazy Electrician,” you need a tool to instantly tell you which wire is the cheapest.

• The Tool: A Min-Heap (Priority Queue).
• Think of this as a “To-Do List” that automatically shuffles the easiest task to the top.
• The Tracker: A Visited set.
• To make sure you don’t wire a house that already has internet (that would be a cycle, and a waste of money).

The Algorithm in Plain English:

1. Create a Min-Heap. Throw your starting node in with a cost of 0.
2. While the Heap is not empty:

• Pop the cheapest node (let’s call it Current).
• If Current is already visited, skip it (don't waste money).
• Mark Current as visited.
• Look at all neighbors of Current.
• If a neighbor is not visited, throw it into the Heap with the cost of that edge.

I have written this as “executable pseudocode” it is valid Java syntax, but simplified to focus on the logic.

I have added comments linking back to the “Lazy Electrician” analogy so you see exactly where the logic happens.

The Setup

We assume you have a Node or an adjacency list where graph[i] contains a list of pairs: {neighbor, weight}.

import java.util.*;

class PrimsAlgorithm {

    // Helper class to store "The Offer" in the Heap
    // We implement Comparable to tell the PriorityQueue how to sort (by cost)
    static class Offer implements Comparable<Offer> {
        int node;
        int cost;

        public Offer(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        // This sorts the heap so the Cheapest cost is always at the top
        public int compareTo(Offer other) {
            return this.cost - other.cost;
        }
    }

    public int minCostConnectPoints(int n, List<List<Offer>> graph) {
        // 1. THE BUCKET (Min-Heap)
        // Automatically sorts offers. Cheapest always on top.
        PriorityQueue<Offer> pq = new PriorityQueue<>();

        // 2. THE CHECKLIST (Visited Set)
        // Tracks which houses already have internet.
        boolean[] visited = new boolean[n];

        // 3. STARTING POINT
        // Pick node 0. It costs $0 to start there.
        pq.add(new Offer(0, 0));

        int totalMSTCost = 0;
        int edgesConnected = 0;

        // 4. THE LOOP (While the bucket is not empty)
        while (!pq.isEmpty()) {

            // Step A: The Grab
            // Take the cheapest offer from the top of the pile.
            Offer current = pq.poll();
            int u = current.node;
            int weight = current.cost;

            // Step B: The "Trash" Logic (CRITICAL)
            // If this node is already visited, this is an old, expensive offer.
            // Throw it away.
            if (visited[u]) {
                continue;
            }

            // Step C: The Connection
            // Mark it as visited (connected). Pay the bill.
            visited[u] = true;
            totalMSTCost += weight;
            edgesConnected++;

            // Optimization: If we connected everyone, we can stop early
            if (edgesConnected == n) break;

            // Step D: The Expansion (Lazy Electrician)
            // Look at all neighbors of the newly connected node 'u'
            for (Offer neighbor : graph.get(u)) {
                int v = neighbor.node;
                int neighborWeight = neighbor.cost;

                // If the neighbor is NOT connected yet, throw the offer in the bucket.
                // We don't check if it's the "best" offer. We just throw it in.
                if (!visited[v]) {
                    pq.add(new Offer(v, neighborWeight));
                }
            }
        }

        return totalMSTCost;
    }
}

Key Java Details to Remember

1. PriorityQueue Default: In Java, a PriorityQueue is a Min-Heap by default (smallest number pops out first). You don't need to configure it specially if you implement Comparable or pass a comparator (a, b) -> a.cost - b.cost.
2. The Adjacency List: The input graph is usually a List<List<Offer>> or List<List<int[]>>. In interviews, it's easier to use an int[] {node, cost} inside the PQ instead of a custom class to save typing time, but the Class method (above) is much easier to read.
3. The continue: Do not forget if (visited[u]) continue;. Without this, you will add the same node's cost multiple times to your total, and your answer will be wrong.

Here are the 3 best LeetCode problems to cement Prim’s Algorithm in your brain.

I have selected these because they graduate in difficulty: one is a textbook example, one is a hidden graph, and one uses a clever trick.

1. The Textbook Definition

Problem: Min Cost to Connect All Points (LeetCode 1584)

• The Vibe: Pure, unadulterated Prim’s.
• The Mission: You are given coordinates (x, y) for several points. You need to connect them all.
• Why it works:
• The Nodes: The points.
• The Edges: The Manhattan Distance (|x_1 — x_2| + |y_1 — y_2|) between every pair of points.
• The Logic: Since you can technically draw a line between any two points, this is a dense graph (lots of edges). Prim’s is actually faster here than Kruskal’s because you don’t have to sort N² edges; you just grow your “infection” from point to point.

2. The “Hidden” MST

Problem: Connecting Cities With Minimum Cost (LeetCode 1135) (Premium, but widely known)

• The Vibe: The “Budget Planner.”
• The Mission: You have N cities and a list of possible roads with costs. Connect everyone. If you can’t, return -1.
• The Twist: Sometimes the graph is broken (disconnected islands).
• Prim’s Check:
• Run Prim’s algorithm exactly as usual.
• The Catch: Keep a count of how many cities you have “infected.” If your infection stops spreading but you haven’t reached $N$ cities yet, it means the remaining cities are unreachable. Return -1.

3. The “Virtual Node” Trick (Mastery Level)

Problem: Optimize Water Distribution in a Village (LeetCode 1168)

• The Vibe: The “Dig or Pipe” Dilemma.
• The Mission: You need to get water to every house. You have two choices for each house:

1. Build a pipe to a neighbor (Cost $X$).
2. Dig a well right there (Cost $Y$).

• Why beginners get stuck: Prim’s usually only handles edges (connecting A to B). It doesn’t handle “node costs” (digging a well at A).
• The Solution (The “Lazy Electrician” Hack):
• Imagine there is a magical “Lake” (Node 0) hidden underground.
• “Digging a well” at House A is actually just building a pipe from Node 0 to Node A.
• Now, you just run standard Prim’s on the whole graph (Houses + Node 0). The algorithm will automatically decide if it’s cheaper to pipe from a neighbor or “pipe” from the magical Lake (dig a well).

How to Practice

Start with LeetCode 1584. It forces you to write the raw algorithm without any tricks. Once you pass that, try 1168 to test if you can adapt the logic to a new scenario.

If you enjoyed this, please give it some claps to help it reach more people. For more stories like this, follow me.