Minimum Spanning Tree Kruskal's Algorithm in DSA Javascript - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You want to connect several computers with cables. Each cable has a cost. You want to connect all computers with the least total cost without any loops.This is called finding a Minimum Spanning Tree (MST) in a network.

🎯 Goal: Build a program that uses Kruskal's algorithm to find the Minimum Spanning Tree of a given network. You will start by creating the list of edges, then set up a helper structure, apply the core logic of Kruskal's algorithm, and finally print the MST edges.

📋 What You'll Learn

Create an array called edges with given edges and costs

Create a parent array to help find connected components

Implement the find and union functions for disjoint sets

Use Kruskal's algorithm to select edges for MST

Print the MST edges in the format node1 - node2 : cost

💡 Why This Matters

🌍 Real World

Network engineers use Minimum Spanning Tree algorithms to design cost-efficient networks connecting computers or devices.

💼 Career

Understanding MST and Kruskal's algorithm is important for roles in network design, optimization, and software engineering involving graph data.

1

Create the list of edges

Create an array called edges with these exact entries: {from: 0, to: 1, cost: 4}, {from: 0, to: 2, cost: 3}, {from: 1, to: 2, cost: 1}, {from: 1, to: 3, cost: 2}, {from: 2, to: 3, cost: 4}, {from: 3, to: 4, cost: 2}, {from: 4, to: 5, cost: 6}

DSA Javascript

// Create the edges array with given objects
// Your code here

Hint

Use an array of objects. Each object has keys from, to, and cost.

2

Create the parent array for disjoint sets

Create an array called parent with 6 elements (for nodes 0 to 5). Initialize each element to its own index (0 to 5).

DSA Javascript

const edges = [
  {from: 0, to: 1, cost: 4},
  {from: 0, to: 2, cost: 3},
  {from: 1, to: 2, cost: 1},
  {from: 1, to: 3, cost: 2},
  {from: 2, to: 3, cost: 4},
  {from: 3, to: 4, cost: 2},
  {from: 4, to: 5, cost: 6}
];

// Create the parent array with values 0 to 5
// Your code here

Hint

Use an array with values from 0 to 5 to represent each node's parent.

3

Implement Kruskal's algorithm core logic

Write the find function that returns the root parent of a node using path compression. Write the union function that connects two nodes if they have different parents. Then, sort the edges array by cost ascending. Create an empty array called mst. Loop over sorted edges and add an edge to mst only if it connects two different sets (use find and union).

DSA Javascript

const edges = [
  {from: 0, to: 1, cost: 4},
  {from: 0, to: 2, cost: 3},
  {from: 1, to: 2, cost: 1},
  {from: 1, to: 3, cost: 2},
  {from: 2, to: 3, cost: 4},
  {from: 3, to: 4, cost: 2},
  {from: 4, to: 5, cost: 6}
];

const parent = [0, 1, 2, 3, 4, 5];

// Write find and union functions
// Sort edges by cost
// Create mst array
// Loop over edges and add to mst if union is successful
// Your code here

Hint

Use path compression in find. In union, connect roots if different. Sort edges by cost ascending. Loop and add edges that connect different sets.

4

Print the Minimum Spanning Tree edges

Use a for loop with variable edge to iterate over mst. Inside the loop, print each edge in the format: edge.from + ' - ' + edge.to + ' : ' + edge.cost.

DSA Javascript

const edges = [
  {from: 0, to: 1, cost: 4},
  {from: 0, to: 2, cost: 3},
  {from: 1, to: 2, cost: 1},
  {from: 1, to: 3, cost: 2},
  {from: 2, to: 3, cost: 4},
  {from: 3, to: 4, cost: 2},
  {from: 4, to: 5, cost: 6}
];

const parent = [0, 1, 2, 3, 4, 5];

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) return false;
  parent[rootB] = rootA;
  return true;
}

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

const mst = [];
for (const edge of edges) {
  if (union(edge.from, edge.to)) {
    mst.push(edge);
  }
}

// Print each edge in mst in the format 'from - to : cost'
// Your code here

Hint

Use a for loop to print each edge in mst with the exact format.

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