Minimum Spanning Tree Prim's Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Prim's Algorithm?

Prim's Algorithm builds the MST by starting from any vertex and repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside it, until all vertices are included.

beginner

In Prim's Algorithm, how do we choose the next edge to add?

We choose the edge with the smallest weight that connects a vertex already in the MST to a vertex not yet in the MST.

intermediate

What data structure is commonly used to efficiently select the next edge in Prim's Algorithm?

A priority queue (or min-heap) is used to efficiently pick the edge with the smallest weight at each step.

intermediate

Why does Prim's Algorithm always produce a Minimum Spanning Tree?

Because it always picks the smallest edge that connects the growing MST to a new vertex, it ensures no cycles and minimal total weight, satisfying MST properties.

What does Prim's Algorithm start with?

A All vertices at once

B The edge with the smallest weight

C Any single vertex

D The vertex with the highest degree

Prim's Algorithm starts from any single vertex and grows the MST by adding edges.

Which data structure helps Prim's Algorithm pick the next edge efficiently?

A Priority Queue (Min-Heap)

B Queue

C Stack

D Linked List

A priority queue (min-heap) helps select the smallest edge quickly.

What condition must an edge satisfy to be added in Prim's Algorithm?

A Is the first edge found

B Connects two vertices already in MST

C Has the largest weight

D Connects a vertex in MST to one outside MST

Edges must connect the MST to a new vertex outside it.

What type of graph is required for Prim's Algorithm to work correctly?

A Connected, weighted graph

B Disconnected graph

C Directed graph

D Unweighted graph

Prim's Algorithm requires a connected, weighted graph.

What is the time complexity of Prim's Algorithm using a priority queue?

A O(V^2)

B O(E log V)

C O(V + E)

D O(log V)

Using a priority queue, Prim's Algorithm runs in O(E log V) time.

Explain step-by-step how Prim's Algorithm builds a Minimum Spanning Tree.

Think about growing the tree one edge at a time.

Describe why Prim's Algorithm guarantees the minimum total edge weight in the spanning tree.

Focus on the choice of edges and MST rules.

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