Minimum Spanning Tree Prim's Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Simple Graph

What is the printed state of the minimum spanning tree edges after running Prim's algorithm on this graph?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, weight int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func prim(graph [][]Edge) []string {
	n := len(graph)
	visited := make([]bool, n)
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: 0, weight: 0})
	visited[0] = true
	result := []string{}

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		current := item.node
		weight := item.weight

		if weight != 0 {
			result = append(result, fmt.Sprintf("Edge to node %d with weight %d", current, weight))
		}

		visited[current] = true

		for _, edge := range graph[current] {
			if !visited[edge.to] {
				heap.Push(pq, Item{node: edge.to, weight: edge.weight})
			}
		}
	}

	return result
}

func main() {
	graph := [][]Edge{
		{{to: 1, weight: 2}, {to: 3, weight: 6}},
		{{to: 0, weight: 2}, {to: 2, weight: 3}, {to: 3, weight: 8}, {to: 4, weight: 5}},
		{{to: 1, weight: 3}, {to: 4, weight: 7}},
		{{to: 0, weight: 6}, {to: 1, weight: 8}, {to: 4, weight: 9}},
		{{to: 1, weight: 5}, {to: 2, weight: 7}, {to: 3, weight: 9}},
	}

	mst := prim(graph)
	for _, edge := range mst {
		fmt.Println(edge)
	}
}

A ["Edge to node 1 with weight 2", "Edge to node 2 with weight 3", "Edge to node 4 with weight 5", "Edge to node 3 with weight 6"]

B ["Edge to node 3 with weight 6", "Edge to node 1 with weight 2", "Edge to node 4 with weight 5", "Edge to node 2 with weight 3"]

C ["Edge to node 1 with weight 2", "Edge to node 3 with weight 8", "Edge to node 4 with weight 9", "Edge to node 2 with weight 7"]

D ["Edge to node 0 with weight 0", "Edge to node 1 with weight 2", "Edge to node 2 with weight 3", "Edge to node 4 with weight 5"]

💡 Hint

Trace the algorithm starting from node 0 and always pick the smallest edge connecting to an unvisited node.

Prim's algorithm starts at node 0, picks the smallest edge to node 1 (weight 2), then from nodes 0 and 1 picks edge to node 2 (weight 3), then edge to node 4 (weight 5), and finally edge to node 3 (weight 6).

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Behavior

Which statement correctly describes Prim's algorithm behavior on a connected weighted graph?

A It sorts all edges first and then picks edges in ascending order to form the MST.

B It grows the minimum spanning tree by adding the smallest edge connecting the tree to a new node.

C It always starts from the node with the smallest edge weight in the graph.

D It removes the largest edges first to avoid cycles in the MST.

💡 Hint

Think about how the tree grows step by step.

Prim's algorithm starts from any node and grows the MST by always adding the smallest edge that connects a new node to the existing tree.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this code produce when running Prim's algorithm on a graph?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, weight int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func prim(graph [][]Edge) []string {
	n := len(graph)
	visited := make([]bool, n)
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: 0, weight: 0})

	result := []string{}

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		current := item.node
		weight := item.weight

		if visited[current] {
			continue
		}

		visited[current] = true

		if weight != 0 {
			result = append(result, fmt.Sprintf("Edge to node %d with weight %d", current, weight))
		}

		for _, edge := range graph[current] {
			if !visited[edge.to] {
				heap.Push(pq, Item{node: edge.to, weight: edge.weight})
			}
		}
	}

	return result
}

func main() {
	graph := [][]Edge{
		{{to: 1, weight: 2}, {to: 3, weight: 6}},
		{{to: 0, weight: 2}, {to: 2, weight: 3}, {to: 3, weight: 8}, {to: 4, weight: 5}},
		{{to: 1, weight: 3}, {to: 4, weight: 7}},
		{{to: 0, weight: 6}, {to: 1, weight: 8}, {to: 4, weight: 9}},
		{{to: 1, weight: 5}, {to: 2, weight: 7}, {to: 3, weight: 9}},
	}

	mst := prim(graph)
	for _, edge := range mst {
		fmt.Println(edge)
	}
}

A The code may include duplicate edges in the MST because it does not check visited nodes before pushing to the priority queue.

B The code causes a runtime panic due to accessing uninitialized slice elements.

C The code causes a syntax error because of missing return statements.

D The code runs correctly and prints the MST edges.

💡 Hint

Check when nodes are marked visited and when edges are pushed to the queue.

The code pushes edges to the priority queue without checking if the node is already visited, which can cause duplicate edges to be processed and included in the MST.

❓ Predict Output

advanced

Output of Prim's Algorithm on a Disconnected Graph

What is the output of running Prim's algorithm on this disconnected graph starting from node 0?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, weight int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func prim(graph [][]Edge) []string {
	n := len(graph)
	visited := make([]bool, n)
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: 0, weight: 0})

	result := []string{}

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		current := item.node
		weight := item.weight

		if visited[current] {
			continue
		}

		visited[current] = true

		if weight != 0 {
			result = append(result, fmt.Sprintf("Edge to node %d with weight %d", current, weight))
		}

		for _, edge := range graph[current] {
			if !visited[edge.to] {
				heap.Push(pq, Item{node: edge.to, weight: edge.weight})
			}
		}
	}

	return result
}

func main() {
	graph := [][]Edge{
		{{to: 1, weight: 4}},
		{{to: 0, weight: 4}},
		{{to: 3, weight: 1}},
		{{to: 2, weight: 1}},
	}

	mst := prim(graph)
	for _, edge := range mst {
		fmt.Println(edge)
	}
}

A ["Edge to node 1 with weight 4", "Edge to node 3 with weight 1"]

B ["Edge to node 0 with weight 0", "Edge to node 1 with weight 4", "Edge to node 2 with weight 1", "Edge to node 3 with weight 1"]

C []

D ["Edge to node 1 with weight 4"]

💡 Hint

Prim's algorithm only visits nodes reachable from the start node.

The graph has two disconnected parts: nodes 0 and 1 connected, and nodes 2 and 3 connected. Starting from node 0, only node 1 is reachable, so only one edge is included.

🚀 Application

expert

Minimum Spanning Tree Weight Calculation

Given the following weighted graph, what is the total weight of the minimum spanning tree found by Prim's algorithm starting at node 0?

DSA Go

package main

import (
	"container/heap"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, weight int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func primTotalWeight(graph [][]Edge) int {
	n := len(graph)
	visited := make([]bool, n)
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: 0, weight: 0})

	totalWeight := 0

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		current := item.node
		weight := item.weight

		if visited[current] {
			continue
		}

		visited[current] = true
		totalWeight += weight

		for _, edge := range graph[current] {
			if !visited[edge.to] {
				heap.Push(pq, Item{node: edge.to, weight: edge.weight})
			}
		}
	}

	return totalWeight
}

func main() {
	graph := [][]Edge{
		{{to: 1, weight: 10}, {to: 2, weight: 6}, {to: 3, weight: 5}},
		{{to: 0, weight: 10}, {to: 3, weight: 15}},
		{{to: 0, weight: 6}, {to: 3, weight: 4}},
		{{to: 0, weight: 5}, {to: 1, weight: 15}, {to: 2, weight: 4}},
	}

	weight := primTotalWeight(graph)
	println(weight)
}

A 25

B 20

C 19

D 15

💡 Hint

Add the weights of edges chosen by Prim's algorithm starting at node 0.

The MST edges are: 0-3 (5), 3-2 (4), and 0-1 (10). Total weight = 5 + 4 + 10 = 19.

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