Minimum Spanning Tree Prim's Algorithm in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the key values for all vertices in Prim's algorithm.

DSA Go

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

Drag options to blanks, or click blank then click option'

A9999

Bint(^uint(0) >> 1)

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing key values to 0 will cause incorrect minimum edge selection.

Using -1 can cause logic errors since weights are positive.

We initialize key values to the maximum integer value to represent infinity before starting Prim's algorithm.

2fill in blank

medium

Complete the code to pick the vertex with the minimum key value not yet included in MST.

DSA Go

func minKey(key []int, mstSet []bool) int {
    min := int(^uint(0) >> 1)
    minIndex := -1
    for v := 0; v < V; v++ {
        if mstSet[v] == false && key[v] < [1] {
            min = key[v]
            minIndex = v
        }
    }
    return minIndex
}

Drag options to blanks, or click blank then click option'

AminIndex

Bkey[v]

Cmin

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing key[v] with key[v] itself is always false.

Using minIndex instead of min causes logic errors.

We compare key[v] with the current minimum value stored in min to find the smallest key.

3fill in blank

hard

Fix the error in the condition to update key values for adjacent vertices in Prim's algorithm.

DSA Go

for v := 0; v < V; v++ {
    if graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < [1] {
        key[v] = graph[u][v]
        parent[v] = u
    }
}

Drag options to blanks, or click blank then click option'

Akey[u]

BmstSet[v]

Cparent[v]

Dkey[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with key[u] instead of key[v] causes wrong updates.

Using mstSet[v] in comparison is logically incorrect.

We compare the edge weight graph[u][v] with the current key[v] to update it if smaller.

4fill in blank

hard

Fill both blanks to complete the loop that constructs the MST result printing parent-child edges.

DSA Go

for i := 1; i < V; i++ {
    fmt.Printf("%d - %d\n", [1], [2])
}

Drag options to blanks, or click blank then click option'

Aparent[i]

Bi

Ckey[i]

DmstSet[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Printing key[i] instead of vertex index causes confusion.

Using mstSet[i] in print statement is incorrect.

We print edges from parent[i] to i to show MST connections.

5fill in blank

hard

Fill all three blanks to complete the main loop of Prim's algorithm updating MST and keys.

DSA Go

for count := 0; count < V-1; count++ {
    u := [1](key, mstSet)
    mstSet[u] = [2]
    for v := 0; v < V; v++ {
        if graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < [3] {
            key[v] = graph[u][v]
            parent[v] = u
        }
    }
}

Drag options to blanks, or click blank then click option'

AminKey

Btrue

Ckey[v]

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Marking mstSet[u] as false instead of true.

Comparing graph[u][v] with key[u] instead of key[v].

We pick the minimum key vertex u, mark it true in mstSet, and update keys for adjacent vertices.

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