Minimum Spanning Tree Prim's Algorithm in DSA Go - 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 so that the total cable length is as short as possible. This is a classic problem solved by finding a Minimum Spanning Tree (MST) of a network graph.The graph is represented by nodes (computers) and weighted edges (cable lengths). You will use Prim's algorithm to find the MST.

🎯 Goal: Build a program that uses Prim's algorithm to find the Minimum Spanning Tree of a given weighted graph. The program will output the edges chosen and the total weight of the MST.

📋 What You'll Learn

Create a graph using an adjacency matrix with exact weights

Use a variable to track the number of vertices

Implement Prim's algorithm to find the MST

Print the edges in the MST and the total weight

💡 Why This Matters

🌍 Real World

Network design, circuit design, and clustering problems often require finding minimum spanning trees to minimize cost.

💼 Career

Understanding MST and Prim's algorithm is important for software engineers working in networking, optimization, and graph algorithms.

1

Create the graph adjacency matrix

Create a 2D slice of integers called graph representing the weighted graph with 5 vertices. Use this exact matrix:
graph := [][]int{
{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 Go

# Create the graph adjacency matrix
# Your code here

Hint

Use a 2D slice of int to represent the graph weights exactly as shown.

2

Add the number of vertices variable

Create an integer variable called V and set it to 5 to represent the number of vertices in the graph.

DSA Go

package main

import "fmt"

func main() {
    graph := [][]int{
        {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},
    }
    // Create variable V for number of vertices
    // Your code here
}

Hint

Use V := 5 to store the number of vertices.

3

Implement Prim's algorithm core logic

Implement Prim's algorithm inside main to find the MST. Use these exact variable names and logic:
- Create a slice key of length V with all values set to 1<<31 - 1 (max int)
- Create a slice mstSet of booleans of length V initialized to false
- Create a slice parent of length V with all values set to -1
- Set key[0] = 0
- Repeat V-1 times:
- Find the vertex u not in mstSet with minimum key[u]
- Mark mstSet[u] = true
- For each vertex v, if graph[u][v] != 0 and mstSet[v] == false and graph[u][v] < key[v], update parent[v] = u and key[v] = graph[u][v]

DSA Go

package main

import "fmt"

func main() {
    graph := [][]int{
        {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},
    }
    V := 5

    // Implement Prim's algorithm core logic here
    // Your code here
}

Hint

Follow the exact steps of Prim's algorithm using the variable names given.

4

Print the MST edges and total weight

Print the edges in the MST and the total weight. Use a for loop from 1 to V-1 and print each edge as parent[i] - i : weight. Then print the total weight as Total weight: X where X is the sum of all edge weights in the MST.

DSA Go

package main

import "fmt"

func main() {
    graph := [][]int{
        {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},
    }
    V := 5

    key := make([]int, V)
    mstSet := make([]bool, V)
    parent := make([]int, V)

    for i := 0; i < V; i++ {
        key[i] = 1<<31 - 1
        mstSet[i] = false
        parent[i] = -1
    }

    key[0] = 0

    for count := 0; count < V-1; count++ {
        min := 1<<31 - 1
        u := -1

        for v := 0; v < V; v++ {
            if mstSet[v] == false && key[v] < min {
                min = key[v]
                u = v
            }
        }

        mstSet[u] = true

        for 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]
            }
        }
    }

    // Print MST edges and total weight
    // Your code here
}

Hint

Loop from 1 to V-1 and print edges using parent[i] and i. Sum weights for total.

Practice

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

easy

A. To find the minimum spanning tree connecting all vertices with minimum total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort the vertices in topological order

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm builds a tree connecting all vertices with the smallest sum of edge weights.

2. Step 2: Compare with other graph algorithms

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

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with minimum total edge weight -> Option A

4. Quick Check:

   Prim's Algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's algorithm
• Thinking it finds shortest paths
• Assuming it detects cycles

2. Which of the following Go code snippets correctly initializes a priority queue for Prim's Algorithm?

easy

A. pq := new(PriorityQueue); pq = nil

B. pq := PriorityQueue{}; pq.Init()

C. pq := make(PriorityQueue, 0); heap.Init(&pq)

D. pq := []int{}; sort.Ints(pq)

Solution

1. Step 1: Check correct priority queue initialization in Go

   PriorityQueue is usually a slice; make with length 0 and call heap.Init(&pq) to initialize.

2. Step 2: Analyze other options

   pq := PriorityQueue{}; pq.Init() misses heap.Init call; C sets pq to nil; D uses slice but sorts, not heap.

3. Final Answer:

   pq := make(PriorityQueue, 0); heap.Init(&pq) -> Option C

4. Quick Check:

   Use make + heap.Init for priority queue [OK]

Hint: Use make and heap.Init to prepare priority queue [OK]

Common Mistakes:

• Forgetting to call heap.Init
• Setting priority queue to nil
• Sorting slice instead of using heap

3. Given the following Go code snippet implementing Prim's Algorithm on a graph with edges:

edges := [][]int{{0,1,2},{1,2,3},{0,2,1}}
// Graph with 3 vertices and edges with weights
// What is the total weight of the minimum spanning tree printed by this code?
func primMST() int {
  n := 3
  graph := make([][]Edge, n)
  for _, e := range edges {
    graph[e[0]] = append(graph[e[0]], Edge{to: e[1], weight: e[2]})
    graph[e[1]] = append(graph[e[1]], Edge{to: e[0], weight: e[2]})
  }
  visited := make([]bool, n)
  pq := &PriorityQueue{}
  heap.Init(pq)
  heap.Push(pq, &Item{vertex: 0, weight: 0})
  total := 0
  for pq.Len() > 0 {
    item := heap.Pop(pq).(*Item)
    if visited[item.vertex] {
      continue
    }
    visited[item.vertex] = true
    total += item.weight
    for _, e := range graph[item.vertex] {
      if !visited[e.to] {
        heap.Push(pq, &Item{vertex: e.to, weight: e.weight})
      }
    }
  }
  return total
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Build the graph and list edges

   Edges: (0-1)=2, (1-2)=3, (0-2)=1. Start from vertex 0 with weight 0.

2. Step 2: Run Prim's Algorithm step-by-step

   Pick 0 (weight 0), add edges (0-1:2), (0-2:1). Next pick edge with smallest weight: (0-2:1), total=1. Then pick (0-1:2), total=3. Vertex 1 and 2 visited, done.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Sum edges 1 + 2 = 3 [OK]

Hint: Pick smallest edges connecting new vertices first [OK]

Common Mistakes:

• Adding all edges instead of minimum spanning tree
• Starting from wrong vertex
• Counting edges twice

4. The following Go code snippet for Prim's Algorithm has a bug. What is the error?

func primBuggy() int {
  n := 3
  graph := make([][]Edge, n)
  // edges omitted for brevity
  visited := make([]bool, n)
  pq := &PriorityQueue{}
  heap.Init(pq)
  heap.Push(pq, &Item{vertex: 0, weight: 0})
  total := 0
  for pq.Len() > 0 {
    item := heap.Pop(pq).(*Item)
    if visited[item.vertex] {
      total += item.weight
      continue
    }
    visited[item.vertex] = true
    for _, e := range graph[item.vertex] {
      if !visited[e.to] {
        heap.Push(pq, &Item{vertex: e.to, weight: e.weight})
      }
    }
  }
  return total
}

medium

A. Not marking vertices as visited

B. Adding edge weight after skipping visited vertex causes incorrect total

C. Not initializing the priority queue with heap.Init

D. Pushing edges with wrong weight values

Solution

1. Step 1: Identify where total is updated

   Total is increased only when visited[item.vertex] is true, which means vertex already visited.

2. Step 2: Understand why this is wrong

   Weights should be added only when vertex is visited first time, not when skipping duplicates.

3. Final Answer:

   Adding edge weight after skipping visited vertex causes incorrect total -> Option B

4. Quick Check:

   Update total only on first visit [OK]

Hint: Add weight only when vertex visited first time [OK]

Common Mistakes:

• Adding weights multiple times for same vertex
• Forgetting to call heap.Init
• Not marking visited vertices

5. You have a weighted undirected graph with 5 vertices and edges:

(0-1, 2), (0-3, 6), (1-2, 3), (1-3, 8), (1-4, 5), (2-4, 7), (3-4, 9)

Using Prim's Algorithm starting from vertex 0, what is the total weight of the minimum spanning tree?

hard

A. 21

B. 19

C. 20

D. 16

Solution

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

   Start at 0: edges (0-1:2), (0-3:6). Pick (0-1:2), total=2.

2. Step 2: Add edges from visited vertices and pick minimum

   Visited: 0,1. Edges: (1-2:3), (1-3:8), (1-4:5), (0-3:6). Pick (1-2:3), total=5.

3. Step 3: Continue adding minimum edges connecting new vertices

   Visited: 0,1,2. Edges: (1-3:8), (1-4:5), (0-3:6), (2-4:7). Pick (1-4:5), total=10.

4. Step 4: Add edges from new vertex 4

   Visited: 0,1,2,4. Edges: (1-3:8), (0-3:6), (2-4:7), (3-4:9). Pick (0-3:6), total=16.

5. Step 5: Add last vertex 3

   Visited all vertices. Total weight = 16.

6. Final Answer:

   16 -> Option D

7. Quick Check:

   Sum edges 2+3+5+6 = 16 [OK]

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

Common Mistakes:

• Choosing edges with larger weights first
• Not updating visited vertices correctly
• Counting edges twice