Minimum Spanning Tree Prim's Algorithm in DSA Typescript - Build from Scratch

Minimum Spanning Tree using Prim's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost without any loops.

🎯 Goal: Build a program that uses Prim's algorithm to find the minimum spanning tree (MST) of a weighted graph representing computers and cable costs.

📋 What You'll Learn

Create a graph as an adjacency matrix with exact weights

Create a variable to track visited nodes

Implement Prim's algorithm core logic to find MST

Print the edges in MST with their weights

💡 Why This Matters

🌍 Real World

Network design to minimize cable costs while connecting all computers.

💼 Career

Understanding MST algorithms is important for roles in network engineering, operations research, and software development involving graph problems.

1

Create the graph as an adjacency matrix

Create a variable called graph as a 2D array (number[][]) with these exact values representing the weighted connections between 5 computers:
[[0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9], [0, 5, 7, 9, 0]]

DSA Typescript

# Your code here

Hint

Use a 2D array with exact rows and columns for the graph weights.

2

Create a visited array to track included nodes

Create a boolean array called visited with 5 elements, all set to false, to track which computers are included in the MST.

DSA Typescript

const graph: number[][] = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0]
];

# Your code here

Hint

Use an array of booleans with 5 false values.

3

Implement Prim's algorithm core logic

Write a function called primMST that:
- Starts from node 0 and marks it visited
- Repeats 4 times to add edges
- Finds the minimum weight edge from visited to unvisited nodes
- Marks the new node visited and stores the edge in mstEdges array as tuples [from, to, weight]
Use variables minWeight, minEdge, and loops with visited and graph inside the function.

DSA Typescript

const graph: number[][] = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0]
];

const visited: boolean[] = [false, false, false, false, false];

// Your code here

Hint

Use nested loops to find the smallest edge connecting visited to unvisited nodes and store edges in an array.

4

Print the edges in the MST

Call the primMST() function and print each edge in the returned array mstEdges in the format: "Edge from X to Y with weight Z".

DSA Typescript

const graph: number[][] = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0]
];

const visited: boolean[] = [false, false, false, false, false];

function primMST(): [number, number, number][] {
  visited[0] = true;
  const mstEdges: [number, number, number][] = [];

  for (let i = 0; i < graph.length - 1; i++) {
    let minWeight = Infinity;
    let minEdge: [number, number] = [-1, -1];

    for (let from = 0; from < graph.length; from++) {
      if (visited[from]) {
        for (let to = 0; to < graph.length; to++) {
          if (!visited[to] && graph[from][to] !== 0 && graph[from][to] < minWeight) {
            minWeight = graph[from][to];
            minEdge = [from, to];
          }
        }
      }
    }

    visited[minEdge[1]] = true;
    mstEdges.push([minEdge[0], minEdge[1], minWeight]);
  }

  return mstEdges;
}

// Your code here

Hint

Call primMST(), then print each edge with template strings.