Minimum Spanning Tree Prim's Algorithm in DSA Go - Execution Trace

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Find edges from MST to non-MST nodes

↓

Select edge with minimum weight

↓

Add connected node to MST

↓

Repeat until all nodes in MST

Start from any node, add it to MST, then repeatedly add the smallest edge connecting MST to a new node until all nodes are included.

Execution Sample

DSA Go

graph := map[string]map[string]int{
  "A": {"B": 2, "C": 3},
  "B": {"A": 2, "C": 1, "D": 1},
  "C": {"A": 3, "B": 1, "D": 4},
  "D": {"B": 1, "C": 4},
}
primMST(graph, "A")

This code runs Prim's algorithm on a graph starting from node A to find the minimum spanning tree.

Execution Table

Step	Operation	Nodes in MST	Edges Considered	Selected Edge	Visual MST State
1	Start at node A	[A]	[A-B(2), A-C(3)]	A-B(2)	A --2-- B
2	Add node B	[A, B]	[B-C(1), B-D(1), A-C(3)]	B-C(1)	A --2-- B --1-- C
3	Add node C	[A, B, C]	[C-D(4), B-D(1)]	B-D(1)	A --2-- B --1-- C | 1 D
4	Add node D	[A, B, C, D]	[]	None	A --2-- B --1-- C | 1 D
5	All nodes included	[A, B, C, D]	[]	None	Final MST: A-B-C-D with edges 2,1,1

💡 All nodes are included in MST, no more edges to add.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
MST Nodes	[]	[A]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, D]
Edges Considered	[]	[A-B(2), A-C(3)]	[B-C(1), B-D(1), A-C(3)]	[C-D(4), B-D(1)]	[]	[]
Selected Edge	None	A-B(2)	B-C(1)	B-D(1)	None	None

Key Moments - 3 Insights

Why do we add edges from the newly added node to the edges considered list?

Because after adding a node to MST, we must consider all edges from MST to non-MST nodes to find the next minimum edge. See execution_table rows 2 and 3 where edges from B and C are added.

Why do we not add edges that connect nodes already in MST?

Edges connecting nodes inside MST would create cycles, which MST must avoid. The algorithm only considers edges connecting MST to nodes outside MST, as shown in the edges considered column.

What happens when no edges are left to consider?

It means all nodes are included in MST and the algorithm stops. This is shown in step 5 where edges considered is empty and MST is complete.

Visual Quiz - 3 Questions

Look at the execution table, which edge is selected at step 3?

A B-D(1)

B B-C(1)

C A-C(3)

D C-D(4)

💡 Hint

Check the 'Selected Edge' column at step 3 in the execution_table.

At which step does node D get added to the MST?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Nodes in MST' column and see when D appears.

If the edge B-D had weight 5 instead of 1, which edge would be selected at step 3?

A B-D(5)

B A-C(3)

C C-D(4)

D No edge, MST complete

💡 Hint

Check edges considered at step 3 and pick the minimum weight edge connecting MST to non-MST nodes.

Concept Snapshot

Prim's Algorithm builds MST by:
- Starting from any node
- Adding the smallest edge connecting MST to new nodes
- Repeating until all nodes included
- Avoiding cycles by only adding edges to non-MST nodes
- Resulting MST has minimum total edge weight

Full Transcript

Prim's algorithm starts from any node and adds it to the MST set. Then it looks at all edges from MST nodes to nodes not yet in MST. It picks the edge with the smallest weight and adds the connected node to MST. This process repeats until all nodes are included. The execution table shows each step: starting at node A, adding nodes B, C, and D in order by selecting minimum edges. The variable tracker shows how MST nodes and edges considered change after each step. Key moments clarify why edges from new nodes are added and why edges inside MST are ignored. The visual quiz tests understanding of edge selection and node addition steps. The concept snapshot summarizes the algorithm's main points.

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