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

Time Complexity: Minimum Spanning Tree Prim's Algorithm

O(V^2)

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 grows.

Specifically, how does the number of steps grow when the graph has more nodes and edges?

Scenario Under Consideration

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

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
}
    

This code finds the minimum spanning tree of a graph using Prim's algorithm with an adjacency matrix.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The outer loop runs once for each vertex (V times).
• Nested operation: Inside, the inner loop checks all vertices to update keys (V times per outer loop).
• Dominant operation: The nested inner loop checking all vertices dominates the time.

How Execution Grows With Input

As the number of vertices (n) grows, the algorithm does more work:

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

Pattern observation: The number of operations grows roughly with the square of the number of vertices.

Final Time Complexity

Time Complexity: O(V2)

This means if the number of vertices doubles, the time to run the algorithm roughly quadruples.

Common Mistake

[X] Wrong: "Prim's algorithm always runs in linear time because it just picks edges one by one."

[OK] Correct: The algorithm checks all vertices repeatedly to find the minimum key, which takes more time as the graph grows, especially with an adjacency matrix.

Interview Connect

Understanding how Prim's algorithm scales helps you explain your choices clearly and shows you know how to handle graphs efficiently in real problems.

Self-Check

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

Practice

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

easy

A. To sort the vertices of a graph

B. To find the minimum spanning tree of a connected weighted graph

C. To detect cycles in a graph

D. To find the shortest path between two nodes

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm is designed to find a tree that connects all vertices with the smallest total edge weight.

2. Step 2: Compare with other graph problems

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

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option B

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always builds a tree with minimum total edge weight [OK]

Common Mistakes:

• Confusing Prim's with shortest path algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

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

easy

A. int key[V]; for(int i=0; i

B. int key[V] = {0};

C. int key[V] = {INT_MAX};

D. int key[V] = NULL;

Solution

1. Step 1: Understand key array purpose

   The key array stores minimum edge weights to include vertices; initially set to a very large value (infinity).

2. Step 2: Check initialization methods

   int key[V]; for(int i=0; i

3. Final Answer:

   int key[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize keys to INT_MAX using loop [OK]

Hint: Use a loop to set all keys to INT_MAX, not zero [OK]

Common Mistakes:

• Initializing key array with zeros
• Using incorrect array initialization syntax
• Assigning NULL to an int array

3. Consider the following adjacency matrix for a graph with 4 vertices:

int graph[4][4] = {
  {0, 2, 0, 6},
  {2, 0, 3, 8},
  {0, 3, 0, 0},
  {6, 8, 0, 0}
};

If Prim's algorithm starts from vertex 0, what is the total weight of the minimum spanning tree?

medium

A. 14

B. 9

C. 11

D. 10

Solution

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

   Edges chosen: 0-1 (2), 1-2 (3), 0-3 (6)

2. Step 2: Sum the weights of chosen edges

   Total weight = 2 + 3 + 6 = 11

3. Step 3: Re-evaluate chosen edges for MST

   Actually, the MST edges are 0-1 (2), 1-2 (3), and 1-3 (8) or 0-3 (6) but 0-3 (6) is better than 1-3 (8). So edges are 0-1 (2), 1-2 (3), 0-3 (6) totaling 11.

4. Step 4: Check if a smaller total weight is possible

   Check edges: 0-1 (2), 1-2 (3), 1-3 (8) sum to 13; 0-1 (2), 1-2 (3), 3-4 (not present); so 11 is correct.

5. Final Answer:

   11 -> Option C

6. Quick Check:

   Sum edges 2+3+6 = 11 [OK]

Hint: Add smallest edges connecting new vertices stepwise [OK]

Common Mistakes:

• Including edges that form cycles
• Adding edges with zero weight incorrectly
• Starting from wrong vertex

4. The following code snippet is part of Prim's algorithm implementation. Identify the error:

for (int count = 0; count < V - 1; count++) {
  int u = minKey(key, mstSet);
  mstSet[u] = true;
  for (int v = 0; v < V; v++) {
    if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
      key[v] = graph[u][v];
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. mstSet[u] should be set to false instead of true

C. The key array is not updated correctly inside the inner loop

D. The condition 'graph[u][v]' should be 'graph[u][v] != 0'

Solution

1. Step 1: Analyze the condition 'graph[u][v]'

   In C, non-zero values are true, zero is false. Using 'graph[u][v]' works but is less clear; better to explicitly check 'graph[u][v] != 0'.

2. Step 2: Check other parts for correctness

   Loop range and key update logic are correct; mstSet[u] should be true to mark visited.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' -> Option D

4. Quick Check:

   Explicit non-zero check improves clarity [OK]

Hint: Use explicit '!= 0' for clarity in conditions [OK]

Common Mistakes:

• Misunderstanding loop ranges
• Incorrectly toggling mstSet flags
• Not updating key array properly

5. Given a graph with vertices and edges as below:

Vertices: 5
Edges:
0 - 1 (2)
0 - 3 (6)
1 - 2 (3)
1 - 3 (8)
1 - 4 (5)
2 - 4 (7)
3 - 4 (9)

If Prim's algorithm starts from vertex 0, which edges will be included in the minimum spanning tree?

hard

A. Edges: 0-1, 1-2, 1-4, 0-3

B. Edges: 0-1, 1-3, 3-4, 2-4

C. Edges: 0-3, 3-4, 1-4, 1-2

D. Edges: 0-1, 1-2, 2-4, 3-4

Solution

1. Step 1: Start from vertex 0 and pick smallest edges stepwise

   Choose 0-1 (2), then from {0,1} choose 1-2 (3), then 1-4 (5), finally 0-3 (6).

2. Step 2: Confirm no cycles and all vertices included

   All vertices 0,1,2,3,4 are connected with minimum total weight edges without cycles.

3. Final Answer:

   Edges: 0-1, 1-2, 1-4, 0-3 -> Option A

4. Quick Check:

   Pick smallest edges connecting new vertices [OK]

Hint: Always pick smallest edge connecting visited to unvisited vertices [OK]

Common Mistakes:

• Choosing edges with larger weights first
• Including edges that create cycles
• Missing to connect all vertices