Minimum Spanning Tree Prim's Algorithm in DSA Python - 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

↓

Pick edge with smallest weight

↓

Add new node to MST set

↓

Repeat until all nodes in MST

Prim's algorithm starts from one node and grows the MST by adding the smallest edge connecting MST to a new node until all nodes are included.

Execution Sample

DSA Python

graph = {
  'A': {'B': 2, 'C': 3},
  'B': {'A': 2, 'C': 1, 'D': 1},
  'C': {'A': 3, 'B': 1, 'D': 4},
  'D': {'B': 1, 'C': 4}
}

# Start from 'A'

This code represents a graph with weighted edges and starts Prim's algorithm from node 'A'.

Execution Table

Step	Operation	Nodes in MST	Edges Considered	Chosen Edge	Visual State
1	Start at node 'A'	['A']	Edges: A-B(2), A-C(3)	None (start)	A |\ B(2) C(3)
2	Pick smallest edge from MST to non-MST	['A', 'B']	Edges: B-C(1), B-D(1), A-C(3)	A-B(2)	A--B \ | C(3) D(not in MST)
3	Pick smallest edge from MST to non-MST	['A', 'B', 'C']	Edges: C-D(4), B-D(1)	B-C(1)	A--B--C \ | D(not in MST)
4	Pick smallest edge from MST to non-MST	['A', 'B', 'C', 'D']	Edges: None (all nodes in MST)	B-D(1)	A--B--C | | D
5	All nodes included	['A', 'B', 'C', 'D']	None	None	MST complete: A-B, B-C, B-D

💡 All nodes are included in MST, algorithm stops.

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)]	[]	[]
Chosen Edge	None	None	A-B(2)	B-C(1)	B-D(1)	None

Key Moments - 3 Insights

Why do we start with just one node in MST?

Prim's algorithm grows MST from a starting node by adding the smallest connecting edge. Starting with one node (Step 1) sets the base for expansion, as shown in execution_table row 1.

How do we decide which edge to pick next?

We pick the smallest weight edge that connects any node in MST to a node outside MST. For example, at Step 3, edges B-C(1) and B-D(1) are considered, and B-C(1) is chosen as smallest (execution_table row 3).

What happens when all nodes are included in MST?

When MST contains all nodes, no edges connect to outside nodes, so the algorithm stops (execution_table row 5).

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, which edge is chosen to add to MST?

A A-B(2)

B A-C(3)

C B-C(1)

D B-D(1)

💡 Hint

Check the 'Chosen Edge' column at Step 2 in execution_table.

At which step does the MST include node 'C'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Nodes in MST' column to see when 'C' appears.

If the edge B-D had weight 5 instead of 1, which edge would be chosen at Step 4?

A B-D(5)

B C-D(4)

C No edge, MST complete

D A-C(3)

💡 Hint

Check edges considered at Step 4 and pick smallest weight connecting MST to non-MST.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node
- Add smallest edge connecting MST to new node
- Repeat until all nodes included
- Uses a set of MST nodes and edge weights
- Greedy approach ensures minimum total weight

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting from one node and repeatedly adding the smallest edge that connects the tree to a new node. We track nodes included in MST and edges considered at each step. The process continues until all nodes are included, ensuring the total edge weight is minimized.

Practice

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

easy

A. To detect cycles in a graph

B. To find the shortest path between two vertices

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

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 minimum total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path, cycle detection, and topological sort serve different purposes than Prim's.

3. Final Answer:

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

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

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

Common Mistakes:

• Confusing Prim's with Dijkstra's shortest path
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following Python data structures is most suitable to efficiently select the next edge with the smallest weight in Prim's algorithm?

easy

A. List

B. Priority Queue (heapq)

C. Dictionary

D. Queue

Solution

1. Step 1: Identify the need for selecting minimum edge

   Prim's algorithm repeatedly selects the edge with the smallest weight.

2. Step 2: Choose data structure for efficient minimum extraction

   Priority Queue (heapq) allows efficient extraction of the smallest element.

3. Final Answer:

   Priority Queue (heapq) -> Option B

4. Quick Check:

   Minimum edge selection = Priority Queue [OK]

Hint: Use heapq for fast minimum edge extraction [OK]

Common Mistakes:

• Using list and scanning all edges each time
• Using queue which is FIFO, not minimum-based
• Using dictionary which doesn't order by weight

3. What is the output of the following Python code implementing Prim's algorithm on the given graph?

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

import heapq

def prim(graph, start=0):
    mst = []
    visited = set([start])
    edges = [(weight, start, to) for to, weight in graph[start]]
    heapq.heapify(edges)

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for to_next, w in graph[to]:
                if to_next not in visited:
                    heapq.heappush(edges, (w, to, to_next))
    return mst

print(prim(graph))

medium

A. [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]

B. [(0, 3, 6), (3, 4, 9), (1, 4, 5), (1, 2, 3)]

C. [(0, 1, 2), (0, 3, 6), (1, 4, 5), (2, 4, 7)]

D. [(1, 2, 3), (2, 4, 7), (0, 3, 6), (1, 4, 5)]

Solution

1. Step 1: Start from vertex 0 and add edges

   Edges from 0: (0-1,2), (0-3,6). Choose smallest: (0-1,2).

2. Step 2: Add edges from vertex 1 and pick next smallest

   From 1: (1-2,3), (1-3,8), (1-4,5). Next smallest edge overall is (1-2,3).

3. Step 3: Continue adding edges and selecting minimum

   Next edges: (1-4,5), (0-3,6). Choose (1-4,5) then (0-3,6).

4. Final Answer:

   [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)] -> Option A

5. Quick Check:

   Edges chosen in ascending weight order form MST [OK]

Hint: Pick edges by smallest weight connecting new vertices [OK]

Common Mistakes:

• Choosing edges with higher weight first
• Adding edges that create cycles
• Not updating visited vertices correctly

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

def prim_bug(graph, start=0):
    mst = []
    visited = set()
    edges = [(0, start, start)]
    while edges:
        weight, frm, to = edges.pop()
        if to not in visited:
            visited.add(to)
            if frm != to:
                mst.append((frm, to, weight))
            for to_next, w in graph[to]:
                if to_next not in visited:
                    edges.append((w, to, to_next))
    return mst

medium

A. The start vertex is never added to visited

B. Visited set is not initialized properly

C. Edges are not added to the list

D. Using list pop() instead of priority queue causes wrong edge selection order

Solution

1. Step 1: Check how edges are selected

   Edges are popped from a list using pop(), which removes the last element, not the smallest weight.

2. Step 2: Understand Prim's requirement for minimum edge selection

   Prim's requires selecting the edge with the smallest weight each time, which needs a priority queue (heap).

3. Final Answer:

   Using list pop() instead of priority queue causes wrong edge selection order -> Option D

4. Quick Check:

   Edge selection order must be by minimum weight [OK]

Hint: Use heapq, not list pop(), to pick minimum edge [OK]

Common Mistakes:

• Using list pop() instead of heapq.heappop()
• Not initializing visited with start vertex
• Appending edges incorrectly

5. Given a weighted undirected graph with vertices 0 to 5 and edges:

0-1: 4, 0-2: 3, 1-2: 1, 1-3: 2, 2-3: 4, 3-4: 2, 4-5: 6

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

hard

A. 9

B. 14

C. 10

D. 12

Solution

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

   Edges from 0: (0-2,3), (0-1,4). Choose (0-2,3).

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

   Visited: {0,2}. Edges: (2-1,1), (0-1,4), (2-3,4). Choose (2-1,1).

3. Step 3: Continue adding edges

   Visited: {0,1,2}. Edges: (1-3,2), (0-1,4), (2-3,4). Choose (1-3,2).

4. Step 4: Add edges from 3

   Visited: {0,1,2,3}. Edges: (3-4,2), (2-3,4), (0-1,4). Choose (3-4,2).

5. Step 5: Add edges from 4

   Visited: {0,1,2,3,4}. Edges: (4-5,6), (2-3,4), (0-1,4). Choose (4-5,6).

6. Step 6: Calculate total weight

   Edges chosen: 3 + 1 + 2 + 2 + 6 = 14.

7. Final Answer:

   14 -> Option A

8. Quick Check:

   Sum of MST edges = 14 [OK]

Hint: Add edges by smallest weight connecting new vertices until all included [OK]

Common Mistakes:

• Including edges that form cycles
• Skipping the smallest connecting edge
• Miscounting total weight