Minimum Spanning Tree Prim's Algorithm in DSA Typescript - Deep Dive

Overview - Minimum Spanning Tree Prim's Algorithm

What is it?

Prim's Algorithm is a way to find the cheapest way to connect all points in a network without any loops. It starts from one point and keeps adding the closest point not yet connected until all points are linked. This creates a tree that covers every point with the smallest total connection cost. It is used on graphs where edges have weights representing costs or distances.

Why it matters

Without Prim's Algorithm, connecting all points in a network cheaply would be very hard and slow, especially for big networks like roads, computer networks, or electrical grids. It helps save money and resources by finding the minimum total cost to connect everything. Without it, networks might be built with unnecessary expensive connections, wasting time and money.

Where it fits

Before learning Prim's Algorithm, you should understand basic graph concepts like nodes, edges, and weights. After this, you can learn other minimum spanning tree algorithms like Kruskal's, and then explore shortest path algorithms like Dijkstra's. This fits into the bigger topic of graph algorithms in data structures.

Mental Model

Core Idea

Prim's Algorithm grows a tree by always adding the cheapest edge that connects a new point to the tree until all points are connected.

Think of it like...

Imagine building a road network starting from your home. Each time, you pick the closest town not yet connected and build a road to it, always choosing the shortest possible new road. You keep doing this until all towns are connected with the least total road length.

Start with one node
  |
  v
[Node A]
  |
  v
Add closest node connected by smallest edge
  |
  v
[Node A]---(2)---[Node B]
  |
  v
Add next closest node connected to tree
  |
  v
[Node A]---(2)---[Node B]
   |               |
  (3)             (1)
   |               |
[Node C]          [Node D]

Edges chosen always have the smallest weight connecting new nodes.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Weights

Concept: Learn what graphs are and how edges can have weights representing cost or distance.

A graph is a set of points called nodes connected by lines called edges. Each edge can have a number called weight that shows how costly or long it is to travel that edge. For example, a map of cities connected by roads with distances is a weighted graph.

Result

You can represent networks with points and weighted connections, which is the base for Prim's Algorithm.

Understanding weighted graphs is essential because Prim's Algorithm uses these weights to find the cheapest connections.

2

Foundation

What is a Spanning Tree?

Concept: A spanning tree connects all nodes in a graph without any loops, using the minimum number of edges.

A tree is a connected graph with no cycles. A spanning tree covers all nodes with the fewest edges possible to keep it connected. For example, if you have 5 cities, a spanning tree connects all 5 with exactly 4 roads and no loops.

Result

You know what a spanning tree is and why it avoids loops while connecting everything.

Knowing what a spanning tree is helps you understand the goal of Prim's Algorithm: to find the cheapest such tree.

3

Intermediate

Starting Prim's Algorithm

🤔Before reading on: do you think Prim's Algorithm starts from the node with the smallest edge or any node? Commit to your answer.

Concept: Prim's Algorithm can start from any node and grows the tree by adding the cheapest edge connecting new nodes.

Pick any node to start. Mark it as part of the tree. Look at all edges from this node to nodes not in the tree. Pick the edge with the smallest weight. Add that edge and the new node to the tree. Repeat until all nodes are included.

Result

You build a tree step-by-step, always adding the cheapest new connection.

Understanding that the start node can be any node shows the algorithm's flexibility and that the process depends on edge weights, not the starting point.

4

Intermediate

Using a Priority Queue for Efficiency

🤔Before reading on: do you think checking all edges every time is efficient or can it be improved? Commit to your answer.

Concept: A priority queue helps pick the smallest edge quickly, improving the algorithm's speed.

Instead of scanning all edges every time, keep edges in a priority queue sorted by weight. When you add a node, add its edges to the queue. Always pick the smallest edge from the queue that connects to a new node. This reduces repeated work.

Result

The algorithm runs faster, especially on large graphs, by quickly finding the next cheapest edge.

Knowing how to use a priority queue reveals how Prim's Algorithm scales well to big networks.

5

Intermediate

Handling Graphs with Different Structures

🤔Before reading on: do you think Prim's Algorithm works on disconnected graphs? Commit to your answer.

Concept: Prim's Algorithm only works on connected graphs; disconnected graphs need special handling.

If the graph is disconnected, Prim's Algorithm will only build a spanning tree for the connected part containing the start node. To cover all nodes, run Prim's separately on each disconnected part or use other algorithms.

Result

You understand the limits of Prim's Algorithm and how to handle disconnected graphs.

Knowing this prevents mistakes when applying Prim's Algorithm to real-world networks that might not be fully connected.

6

Advanced

Implementing Prim's Algorithm in TypeScript

🤔Before reading on: do you think the algorithm needs to track visited nodes explicitly or can it rely on the priority queue alone? Commit to your answer.

Concept: A complete implementation tracks visited nodes and uses a priority queue to pick edges efficiently.

```typescript class Edge { constructor(public to: number, public weight: number) {} } function prim(graph: Edge[][]): string { const n = graph.length; const visited = new Array(n).fill(false); const minHeap: {node: number; weight: number}[] = []; let result = ''; function pushEdges(node: number) { visited[node] = true; for (const edge of graph[node]) { if (!visited[edge.to]) { minHeap.push({node: edge.to, weight: edge.weight}); } } } // Simple priority queue by sorting (for clarity) function popMin() { minHeap.sort((a, b) => a.weight - b.weight); return minHeap.shift(); } pushEdges(0); // start from node 0 while (minHeap.length > 0) { const edge = popMin(); if (edge && !visited[edge.node]) { result += `${edge.weight} -> `; pushEdges(edge.node); } } return result + 'null'; } // Example graph const graph: Edge[][] = [ [new Edge(1, 2), new Edge(3, 6)], [new Edge(0, 2), new Edge(2, 3), new Edge(3, 8), new Edge(4, 5)], [new Edge(1, 3), new Edge(4, 7)], [new Edge(0, 6), new Edge(1, 8), new Edge(4, 9)], [new Edge(1, 5), new Edge(2, 7), new Edge(3, 9)] ]; console.log(prim(graph)); ``` This prints the weights of edges added in order.

Result

"2 -> 3 -> 5 -> 6 -> null"

Seeing a full implementation connects theory to practice and shows how to manage visited nodes and edge selection.

7

Expert

Surprising Behavior with Equal Edge Weights

🤔Before reading on: do you think Prim's Algorithm always produces the same tree if multiple edges have the same weight? Commit to your answer.

Concept: When edges have equal weights, Prim's Algorithm can produce different valid minimum spanning trees depending on the order of edge selection.

If multiple edges have the same smallest weight, the algorithm picks one based on implementation details like queue order. This means the final tree might differ but still have the same total cost. This is important when deterministic output is needed.

Result

You realize that minimum spanning trees are not always unique and implementation choices affect the result.

Understanding this prevents confusion when different runs produce different trees but the same cost.

Under the Hood

Prim's Algorithm maintains a set of nodes included in the tree and a priority queue of edges connecting the tree to nodes outside it. At each step, it extracts the edge with the smallest weight from the queue that connects to a new node, adds that node to the tree, and inserts its edges into the queue. This process continues until all nodes are included. Internally, the priority queue ensures efficient selection of the next edge, and a visited set prevents cycles.

Why designed this way?

Prim's Algorithm was designed to find a minimum spanning tree efficiently by growing it one node at a time, avoiding cycles by tracking visited nodes. It uses a greedy approach, always choosing the cheapest next edge, which guarantees an optimal solution for connected weighted graphs. Alternatives like Kruskal's sort edges globally, but Prim's focuses on local growth, which can be more efficient for dense graphs.

┌───────────────┐
│ Start with one│
│ node in tree  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Add edges from│
│ this node to  │
│ priority queue│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Extract edge  │
│ with smallest │
│ weight        │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ If edge leads │
│ to new node,  │
│ add node to   │
│ tree          │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Repeat until  │
│ all nodes in  │
│ tree          │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does Prim's Algorithm always start from the node with the smallest edge? Commit to yes or no.

Common Belief: Prim's Algorithm must start from the node with the smallest edge to work correctly.

Reality: Prim's Algorithm can start from any node; the final minimum spanning tree cost remains the same.

Why it matters: Believing this limits understanding and causes confusion about the algorithm's flexibility and correctness.

Quick: Does Prim's Algorithm work on disconnected graphs to connect all nodes? Commit to yes or no.

Common Belief: Prim's Algorithm can find a minimum spanning tree for any graph, connected or not.

Reality: Prim's Algorithm only works on connected graphs; disconnected graphs require running it on each component separately.

Why it matters: Applying Prim's to disconnected graphs without this knowledge leads to incomplete solutions and errors.

Quick: Is the minimum spanning tree unique if multiple edges have the same weight? Commit to yes or no.

Common Belief: The minimum spanning tree is always unique for a given graph.

Reality: Minimum spanning trees may not be unique if multiple edges have equal weights; different valid trees can exist.

Why it matters: Expecting uniqueness can cause confusion when different runs produce different trees with the same cost.

Expert Zone

1

Prim's Algorithm's performance depends heavily on the data structure used for the priority queue; using a binary heap or Fibonacci heap can drastically improve speed.

2

The choice of starting node can affect the shape of the resulting minimum spanning tree but not its total cost.

3

In dense graphs, Prim's Algorithm is often more efficient than Kruskal's because it avoids sorting all edges globally.

When NOT to use

Prim's Algorithm is not suitable for disconnected graphs without modifications; Kruskal's Algorithm or running Prim's on each component is better. For very sparse graphs, Kruskal's with a union-find structure may be faster. Also, if you need to find shortest paths rather than spanning trees, algorithms like Dijkstra's are more appropriate.

Production Patterns

In real-world networks like electrical grids or communication networks, Prim's Algorithm is used to design cost-effective layouts. It is often combined with heuristics to handle dynamic changes or constraints. Implementations use efficient priority queues and adjacency lists to handle large-scale graphs.

Connections

Kruskal's Algorithm

Both find minimum spanning trees but use different approaches; Prim's grows a tree locally, Kruskal's sorts edges globally.

Understanding both algorithms helps choose the best one based on graph density and structure.

Greedy Algorithms

Prim's Algorithm is a classic example of a greedy algorithm that makes the best local choice at each step.

Knowing greedy principles clarifies why Prim's Algorithm guarantees an optimal solution for minimum spanning trees.

Network Design in Civil Engineering

Prim's Algorithm models how to build road or utility networks with minimal total cost.

Seeing this connection shows how abstract algorithms solve real-world infrastructure problems.

Common Pitfalls

#1 Not tracking visited nodes leads to cycles and incorrect trees.

Wrong approach:

while (minHeap.length > 0) {
const edge = popMin();
// Missing visited check
result += `${edge.weight} -> `;
pushEdges(edge.node);
}

Correct approach:

while (minHeap.length > 0) {
const edge = popMin();
if (!visited[edge.node]) {
result += `${edge.weight} -> `;
pushEdges(edge.node);
}
}

Root cause:

Forgetting to check if a node is already in the tree causes adding edges that create loops.

#2 Starting from a node not in the graph or invalid index causes errors.

Wrong approach:

pushEdges(graph.length); // invalid start node index

Correct approach:

pushEdges(0); // valid start node index

Root cause:

Misunderstanding node indexing or graph size leads to runtime errors.

#3 Using an unsorted list instead of a priority queue makes the algorithm inefficient.

Wrong approach:

minHeap.push(...); // but never sort or extract min properly

Correct approach:

Use a priority queue or sort minHeap before extracting the smallest edge.

Root cause:

Not managing edge selection efficiently causes slow performance on large graphs.

Key Takeaways

Prim's Algorithm builds a minimum spanning tree by growing it one node at a time, always adding the cheapest edge connecting new nodes.

It works only on connected weighted graphs and requires tracking visited nodes to avoid cycles.

Using a priority queue to select edges efficiently is key to scaling the algorithm to large graphs.

Minimum spanning trees may not be unique if edges have equal weights, and the starting node can be any node.

Prim's Algorithm is a practical greedy approach widely used in network design and graph problems.

Practice

1. What is the main goal of Prim's algorithm in graph theory?

easy

A. To find the minimum spanning tree connecting all vertices with the least total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree connecting all vertices with minimum total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path and cycle detection are different problems; Prim's focuses on spanning tree.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option A

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's algorithm
• Thinking it finds shortest path
• Assuming it detects cycles

2. Which of the following is the correct way to initialize the key array in Prim's algorithm in TypeScript?

easy

A. const key: number[] = Array(n).fill(0);

B. const key: number[] = new Array(n).fill(Infinity);

C. const key: number[] = new Array(n).fill(null);

D. const key: number[] = Array(n).fill(-1);

Solution

1. Step 1: Understand key array role

   Key array stores minimum edge weights; initialize with Infinity to find minimum.

2. Step 2: Check initialization options

   Filling with Infinity ensures any edge weight will be smaller initially.

3. Final Answer:

   const key: number[] = new Array(n).fill(Infinity); -> Option B

4. Quick Check:

   Initialize keys with Infinity for minimum comparison [OK]

Hint: Use Infinity to initialize keys for minimum edge weight tracking [OK]

Common Mistakes:

• Initializing keys with 0 causes wrong minimum comparisons
• Using null instead of a number
• Filling with -1 which is invalid for weights

3. Consider the following TypeScript code snippet implementing Prim's algorithm on a graph with 4 vertices. What is the printed MST total weight?

const graph = [
  [0, 2, 0, 6],
  [2, 0, 3, 8],
  [0, 3, 0, 0],
  [6, 8, 0, 0]
];

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count < n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

    for (let v = 0; v < n; v++) {
      if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return totalWeight;
}

console.log(primMST(graph));

medium

A. 11

B. 9

C. 14

D. 10

Solution

1. Step 1: Trace MST selection steps

   Start with vertex 0: key[0]=0, others Infinity. Select vertex 0 (weight 0), add edges: 2 (to 1), 6 (to 3).

2. Step 2: Select next minimum edge

   Choose vertex 1 (key=2), add edge weight 2. Update keys: vertex 2 gets 3 (edge 1-2), vertex 3 remains 6.

3. Step 3: Select next minimum edge

   Choose vertex 2 (key=3), add edge weight 3. Vertex 3 key remains 6.

4. Step 4: Select last vertex

   Choose vertex 3 (key=6), add edge weight 6.

5. Step 5: Calculate total weight

   Total = 2 + 3 + 6 = 11

6. Final Answer:

   11 -> Option A

7. Quick Check:

   MST total weight = 11 [OK]

Hint: Add chosen edge weights stepwise to get MST total [OK]

Common Mistakes:

• Forgetting to add the first vertex key (0) to total
• Adding all edges instead of MST edges
• Mixing up vertex indices

4. The following TypeScript code for Prim's algorithm has a bug. What is the error?

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count <= n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

    for (let v = 0; v < n; v++) {
      if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return totalWeight;
}

medium

A. The inner loop condition should be v <= n

B. The key array is not initialized correctly

C. The mstSet array should be initialized with true values

D. The outer loop runs one extra time causing an invalid vertex selection

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to n inclusive (<= n - 1), which means n iterations instead of n-1.

2. Step 2: Understand impact of extra iteration

   Extra iteration causes selection of u = -1 (no valid vertex), leading to errors or invalid updates.

3. Final Answer:

   The outer loop runs one extra time causing an invalid vertex selection -> Option D

4. Quick Check:

   Loop count must be n-1, not n [OK]

Hint: Outer loop should run n-1 times, not n [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing mstSet incorrectly
• Changing inner loop bounds wrongly

5. Given a weighted undirected graph represented by the adjacency matrix below, apply Prim's algorithm starting from vertex 0. Which edges are included in the MST?

const graph = [
  [0, 1, 4, 0, 0, 0],
  [1, 0, 4, 2, 7, 0],
  [4, 4, 0, 3, 5, 0],
  [0, 2, 3, 0, 4, 6],
  [0, 7, 5, 4, 0, 7],
  [0, 0, 0, 6, 7, 0]
];

Options list edges as pairs (u-v):

hard

A. (0-2), (2-3), (3-1), (3-4), (4-5)

B. (0-1), (1-3), (3-5), (5-4), (4-2)

C. (0-1), (1-3), (3-2), (3-4), (3-5)

D. (0-1), (1-2), (2-3), (3-4), (4-5)

Solution

1. Step 1: Start from vertex 0 and pick minimum edges

   From 0, edges: (0-1)=1, (0-2)=4. Choose (0-1) with weight 1.

2. Step 2: Update keys and select next minimum edge

   From vertices {0,1}, edges: (1-3)=2, (1-2)=4, (0-2)=4. Choose (1-3) with weight 2.

3. Step 3: Continue selecting minimum edges connecting MST

   From {0,1,3}, edges: (3-2)=3, (3-4)=4, (3-5)=6. Choose (3-2) with weight 3.

4. Step 4: Next minimum edge from MST

   From {0,1,2,3}, edges: (3-4)=4, (3-5)=6. Choose (3-4) with weight 4.

5. Step 5: Final edge to include

   From {0,1,2,3,4}, edges: (3-5)=6, (4-5)=7. Choose (3-5) with weight 6.

6. Final Answer:

   (0-1), (1-3), (3-2), (3-4), (3-5) -> Option C

7. Quick Check:

   Edges chosen minimize total weight connecting all vertices [OK]

Hint: Pick smallest connecting edge each step starting from vertex 0 [OK]

Common Mistakes:

• Choosing edges with larger weights early
• Not updating keys after adding vertices
• Assuming linear chain instead of MST shape