Minimum Spanning Tree Kruskal's Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Minimum Spanning Tree Kruskal's Algorithm

O(m log m)

Understanding Time Complexity

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

Specifically, how does the number of edges and vertices affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function kruskal(edges, vertices) {
  edges.sort((a, b) => a.weight - b.weight);
  const parent = Array(vertices).fill(0).map((_, i) => i);
  const rank = Array(vertices).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
      if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
      else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
      else {
        parent[rootB] = rootA;
        rank[rootA]++;
      }
      return true;
    }
    return false;
  }

  const mst = [];
  for (const edge of edges) {
    if (union(edge.u, edge.v)) mst.push(edge);
  }
  return mst;
}
    

This code sorts edges by weight, then uses union-find to add edges without cycles, building the minimum spanning tree.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting all edges by weight.
• How many times: Sorting runs once on all edges, which is m edges.
• Secondary operation: Union-find operations inside a loop over all edges.
• How many times: Each edge is processed once, so up to m times.
• Union-find find calls: Each find uses path compression, making it almost constant amortized time per call.

How Execution Grows With Input

As the number of edges m and vertices n grow, the sorting step takes more time, and union-find operations increase linearly.

Input Size (n, m)	Approx. Operations
n=10, m=15	Sorting ~ 15 log 15 ≈ 60, Union-find ~ 15
n=100, m=500	Sorting ~ 500 log 500 ≈ 4500, Union-find ~ 500
n=1000, m=5000	Sorting ~ 5000 log 5000 ≈ 65000, Union-find ~ 5000

Pattern observation: Sorting dominates and grows a bit faster than linearly, while union-find grows linearly.

Final Time Complexity

Time Complexity: O(m log m)

This means the time mainly depends on sorting the edges, which grows a bit faster than the number of edges.

Common Mistake

[X] Wrong: "The union-find operations take as much time as sorting."

[OK] Correct: Union-find with path compression is almost constant amortized time per operation, so sorting is the real time cost.

Interview Connect

Understanding Kruskal's time complexity helps you explain how efficient your solution is and shows you can analyze algorithms beyond just coding them.

Self-Check

"What if the edges were already sorted? How would that change the time complexity?"

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To find the minimum spanning tree of a graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand Kruskal's Algorithm purpose

   Kruskal's Algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph problems

   Shortest path and cycle detection are different problems solved by other algorithms like Dijkstra or DFS, not Kruskal's.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option A

4. Quick Check:

   Minimum Spanning Tree = Kruskal's Algorithm goal [OK]

Hint: Kruskal connects all nodes with least total edge weight [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking Kruskal detects cycles only
• Assuming it sorts vertices

2. Which of the following is the correct way to sort edges by weight in JavaScript for Kruskal's Algorithm?

easy

A. edges.sort((a, b) => a.weight * b.weight);

B. edges.sort((a, b) => b.weight - a.weight);

C. edges.sort((a, b) => a.weight + b.weight);

D. edges.sort((a, b) => a.weight - b.weight);

Solution

1. Step 1: Understand sorting for MST

   Kruskal's Algorithm requires edges sorted in ascending order by weight to pick smallest edges first.

2. Step 2: Check JavaScript sort syntax

   Using edges.sort((a, b) => a.weight - b.weight); sorts edges from smallest to largest weight correctly.

3. Final Answer:

   edges.sort((a, b) => a.weight - b.weight); -> Option D

4. Quick Check:

   Sort ascending by weight = edges.sort((a, b) => a.weight - b.weight); [OK]

Hint: Sort edges ascending by weight using (a,b) => a.weight - b.weight [OK]

Common Mistakes:

• Sorting descending instead of ascending
• Using addition or multiplication in sort callback
• Not returning a number in sort function

3. Consider the following edges of a graph:
const edges = [ {from: 'A', to: 'B', weight: 1}, {from: 'B', to: 'C', weight: 4}, {from: 'A', to: 'C', weight: 3}, {from: 'C', to: 'D', weight: 2} ];
After applying Kruskal's Algorithm, which edges will be included in the MST?

medium

A. [{A-B,1}, {A-C,3}, {B-C,4}]

B. [{A-B,1}, {C-D,2}, {A-C,3}]

C. [{A-B,1}, {C-D,2}, {B-C,4}]

D. [{B-C,4}, {A-C,3}, {C-D,2}]

Solution

1. Step 1: Sort edges by weight ascending

   Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-C,4)

2. Step 2: Pick edges without forming cycles

   Pick A-B (1), then C-D (2), then A-C (3). Adding B-C (4) would form a cycle, so skip it.

3. Final Answer:

   [{A-B,1}, {C-D,2}, {A-C,3}] -> Option B

4. Quick Check:

   Edges with smallest weights and no cycles = [{A-B,1}, {C-D,2}, {A-C,3}] [OK]

Hint: Pick edges ascending weight, skip if cycle forms [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges before selection
• Choosing heavier edges unnecessarily

4. The following code snippet tries to implement Kruskal's Algorithm but has a bug:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 2},
  {from: 'A', to: 'C', weight: 3}
];

edges.sort((a, b) => a.weight - b.weight);

const mst = [];
const visited = new Set();

for (const edge of edges) {
  if (!visited.has(edge.from) || !visited.has(edge.to)) {
    mst.push(edge);
    visited.add(edge.from);
    visited.add(edge.to);
  }
}
console.log(mst);

What is the main issue with this code?

medium

A. It does not correctly check for cycles, so MST may be incorrect

B. The edges are not sorted properly

C. The visited set is not initialized

D. It uses an array instead of a linked list for MST

Solution

1. Step 1: Analyze cycle detection logic

   The code uses a visited set to check if nodes are visited, but this does not detect cycles correctly in Kruskal's Algorithm.

2. Step 2: Understand correct cycle detection

   Kruskal's requires a Union-Find or Disjoint Set data structure to detect cycles properly, not just visited nodes.

3. Final Answer:

   It does not correctly check for cycles, so MST may be incorrect -> Option A

4. Quick Check:

   Cycle detection needs Union-Find, not visited set [OK]

Hint: Use Union-Find to detect cycles, not visited nodes [OK]

Common Mistakes:

• Using visited set for cycle detection
• Ignoring cycle checks
• Assuming sorting fixes all issues

5. You have a graph with vertices ['A', 'B', 'C', 'D', 'E'] and edges:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 3},
  {from: 'A', to: 'C', weight: 2},
  {from: 'C', to: 'D', weight: 4},
  {from: 'D', to: 'E', weight: 5},
  {from: 'B', to: 'E', weight: 6}
];

Using Kruskal's Algorithm with a Union-Find structure, what is the total weight of the minimum spanning tree?

hard

A. 10

B. 15

C. 12

D. 16

Solution

1. Step 1: Sort edges by weight ascending

   Sorted edges: (A-B,1), (A-C,2), (B-C,3), (C-D,4), (D-E,5), (B-E,6)

2. Step 2: Pick edges without cycles using Union-Find

   Pick A-B(1), A-C(2), B-C(3) forms cycle, skip B-C. Pick C-D(4), D-E(5). Total weight = 1+2+4+5 = 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Sum of MST edges = 12 [OK]

Hint: Sum smallest edges without cycles using Union-Find [OK]

Common Mistakes:

• Including edges that form cycles
• Adding all edges without checking
• Misordering edges before selection