Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript - 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.

🎯 Goal: Build a program that finds the minimum total cost to connect all computers using Kruskal's algorithm.

📋 What You'll Learn

Create an array of edges with exact weights and nodes

Create a parent array for union-find structure

Implement the union-find functions: find and union

Sort edges by weight

Use Kruskal's algorithm to select edges without cycles

Print the total cost of the minimum spanning tree

💡 Why This Matters

🌍 Real World

Network design, connecting computers or cities with minimum cable or road cost.

💼 Career

Useful for software engineers working on network optimization, infrastructure planning, and graph algorithms.

1

Create the graph edges

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

DSA Typescript

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

Hint

Use an array of objects with keys from, to, and weight.

2

Create the parent array for union-find

Create an array called parent with length 6 where each element is its own index (0 to 5).

DSA Typescript

const edges = [
  {from: 0, to: 1, weight: 4},
  {from: 0, to: 2, weight: 3},
  {from: 1, to: 2, weight: 1},
  {from: 1, to: 3, weight: 2},
  {from: 2, to: 3, weight: 4},
  {from: 3, to: 4, weight: 2},
  {from: 4, to: 5, weight: 6}
]
// Create the parent array for union-find
// Your code here

Hint

Each node is its own parent initially.

3

Implement union-find and Kruskal's algorithm

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. Sort the edges array by weight. Use a for loop to iterate over edges and add the edge's weight to totalCost if union returns true.

DSA Typescript

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

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

// Write find and union functions
// Sort edges by weight
// Use for loop to build MST and calculate totalCost
// Your code here

Hint

Use path compression in find. In union, connect roots if different. Sort edges by weight ascending. Add edge weight to totalCost only if union succeeds.

4

Print the total cost of the minimum spanning tree

Write console.log(totalCost) to display the total cost of the minimum spanning tree.

DSA Typescript

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

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

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

function union(a: number, b: number): boolean {
  const rootA = find(a)
  const rootB = find(b)
  if (rootA === rootB) return false
  parent[rootB] = rootA
  return true
}

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

let totalCost = 0
for (const edge of edges) {
  if (union(edge.from, edge.to)) {
    totalCost += edge.weight
  }
}

// Print the totalCost
// Your code here

Hint

The minimum total cost to connect all computers is 14.