Minimum Spanning Tree Prim's Algorithm in DSA Typescript - Time & Space Complexity

Time Complexity: Minimum Spanning Tree Prim's Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find a minimum spanning tree using Prim's algorithm changes as the graph size grows.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following Prim's algorithm code snippet.

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

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

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

This code finds the minimum spanning tree weights for a graph represented by an adjacency matrix.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: The outer loop runs once for each node (n times).
• Inside it: A loop to find the minimum key value among nodes not yet in MST (runs n times).
• Another loop: Updates keys for neighbors of the chosen node (runs n times).
• Dominant work: The nested loops inside the outer loop, each running up to n times, dominate the cost.

How Execution Grows With Input

As the number of nodes (n) grows, the loops multiply work roughly by n * n.

Input Size (n)	Approx. Operations
10	About 100 operations
100	About 10,000 operations
1000	About 1,000,000 operations

Pattern observation: The work grows roughly with the square of the number of nodes.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of nodes, the time needed roughly quadruples.

Common Mistake

[X] Wrong: "Prim's algorithm always runs in linear time O(n)."

[OK] Correct: The nested loops cause the time to grow with the square of nodes, not just linearly.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why certain data structures can improve performance.

Self-Check

"What if we used a priority queue (min-heap) to select the minimum key instead of scanning all nodes? How would the time complexity change?"

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