Minimum spanning tree (Prim's) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Minimum spanning tree (Prim's)

Start with any node

↓

Add node to MST set

↓

Find all edges from MST to non-MST nodes

↓

Pick edge with smallest weight

↓

Add connected node to MST

↓

Repeat until all nodes included

Prim's algorithm builds the minimum spanning tree by starting from one node and repeatedly adding the smallest edge that connects the tree to a new node.

Execution Sample

Data Structures Theory

Graph edges:
A-B:2, A-C:3, B-C:1, B-D:4, C-D:5
Start at A
Add smallest edge connecting MST to new node
Repeat until all nodes included

This example shows Prim's algorithm starting at node A and adding edges step-by-step to build the minimum spanning tree.

Analysis Table

Step	Operation	MST Nodes	Edges Considered	Edge Chosen	MST Edges	Visual State
1	Start at node A	[A]	Edges from A: A-B(2), A-C(3)	None	None	MST: A
2	Choose smallest edge from MST to non-MST	[A]	A-B(2), A-C(3)	A-B(2)	[A-B]	MST: A - B
3	Add node B to MST	[A, B]	Edges from A,B: A-C(3), B-C(1), B-D(4)	B-C(1)	[A-B, B-C]	MST: A - B - C
4	Add node C to MST	[A, B, C]	Edges from A,B,C: B-D(4), C-D(5)	B-D(4)	[A-B, B-C, B-D]	MST: A - B - C | D
5	Add node D to MST	[A, B, C, D]	All nodes included	None	[A-B, B-C, B-D]	MST complete: A-B, B-C, B-D
6	Stop	[A, B, C, D]	No edges left	None	[A-B, B-C, B-D]	All nodes connected, MST done

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

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
MST Nodes	[]	[A]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, D]
Edges Considered	Edges from A	Edges from A,B	Edges from A,B,C	All nodes included	None	None
MST Edges	[]	[A-B]	[A-B, B-C]	[A-B, B-C, B-D]	[A-B, B-C, B-D]	[A-B, B-C, B-D]

Key Insights - 3 Insights

Why do we only consider edges that connect MST nodes to non-MST nodes?

Because Prim's algorithm grows the MST by adding new nodes connected by the smallest edge from the existing MST. Considering edges only between MST and non-MST nodes prevents cycles and ensures all nodes get connected.

What happens if we pick an edge that connects two nodes already in MST?

Picking such an edge would create a cycle, which is not allowed in a spanning tree. The execution_table shows edges chosen always connect MST to a new node.

Why does the algorithm stop when all nodes are included in MST?

Because the MST must include all nodes with the minimum total edge weight. Once all nodes are in MST, no more edges need to be added, as shown in the last step of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. Which edge is chosen to add node C to MST?

A A-C with weight 3

B B-C with weight 1

C B-D with weight 4

D C-D with weight 5

💡 Hint

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

At which step does the MST include all nodes?

A Step 5

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'MST Nodes' column to see when all nodes [A, B, C, D] are included.

If the edge B-C had weight 6 instead of 1, which edge would be chosen at Step 3?

A B-D with weight 4

B B-C with weight 6

C A-C with weight 3

D C-D with weight 5

💡 Hint

Compare edge weights in 'Edges Considered' at Step 3 and pick the smallest.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node
- Add smallest edge connecting MST to new node
- Repeat until all nodes included
- Avoid cycles by only connecting MST to non-MST nodes
- Result is a tree connecting all nodes with minimum total edge weight

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting at any node and repeatedly adding the smallest edge that connects the current tree to a new node. At each step, it considers edges from nodes already in the MST to nodes not yet included. It picks the smallest such edge and adds the connected node to the MST. This process repeats until all nodes are included. The execution table shows step-by-step how nodes and edges are added, ensuring no cycles form and the total edge weight is minimized. Key points include only considering edges connecting MST to non-MST nodes and stopping when all nodes are included. The visual quiz tests understanding of edge choices and MST growth.

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 the least total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree that connects all vertices with the minimum sum of edge weights.

2. Step 2: Compare with other graph problems

   Unlike shortest path or cycle detection, Prim's focuses on spanning all vertices with minimal total edge cost.

3. Final Answer:

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

4. Quick Check:

   Prim's algorithm = Minimum spanning tree [OK]

Hint: Prim's always finds the cheapest tree connecting all points [OK]

Common Mistakes:

• Confusing minimum spanning tree with shortest path
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which data structure is commonly used in Prim's algorithm to select the next edge with the smallest weight?

easy

A. Priority queue (min-heap)

B. Stack

C. Queue

D. Hash table

Solution

1. Step 1: Identify how Prim's picks edges

   Prim's algorithm always picks the edge with the smallest weight connecting the tree to a new vertex.

2. Step 2: Choose the right data structure

   A priority queue (min-heap) efficiently retrieves the smallest edge weight at each step.

3. Final Answer:

   Priority queue (min-heap) -> Option A

4. Quick Check:

   Smallest edge selection = Priority queue [OK]

Hint: Use a min-heap to always pick the cheapest edge next [OK]

Common Mistakes:

• Using stack or queue which don't sort by weight
• Confusing hash table with priority queue
• Ignoring edge weights in selection

3. Consider the following weighted graph edges:
A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-D: 5
Using Prim's algorithm starting from vertex A, what is the total weight of the minimum spanning tree?

medium

A. 5

B. 8

C. 7

D. 6

Solution

1. Step 1: Start from vertex A and pick smallest edge

   Edges from A: A-B(2), A-C(3). Pick A-B with weight 2.

2. Step 2: Add next smallest edge connecting new vertices

   From B and A, edges are B-C(1), B-D(4), A-C(3). Pick B-C with weight 1.

3. Step 3: Add next smallest edge to connect remaining vertex D

   Edges from B, C, A to D: B-D(4), C-D(5). Pick B-D with weight 4.

4. Step 4: Calculate total weight

   Total = 2 + 1 + 4 = 7.

5. Final Answer:

   7 -> Option C

6. Quick Check:

   Sum edges 2+1+4 = 7 [OK]

Hint: Add edges with smallest weight connecting new vertices [OK]

Common Mistakes:

• Choosing edges without checking if vertex is already included
• Adding edges that form cycles
• Forgetting to sum all chosen edges

4. In the following code snippet for Prim's algorithm, what is the error?

graph = { 'A': {'B': 2, 'C': 3}, 'B': {'A': 2, 'C': 1, 'D': 4}, 'C': {'A': 3, 'B': 1, 'D': 5}, 'D': {'B': 4, 'C': 5} }
visited = set()
keys = {v: float('inf') for v in graph}
keys['A'] = 0
while len(visited) < len(graph):
    u = min((k for k in keys if k not in visited), key=lambda x: keys[x])
    visited.add(u)
    for v, w in graph[u].items():
        if v not in visited and w < keys[v]:
            keys[v] = w

medium

A. The keys dictionary is not updated correctly

B. The algorithm does not track parent nodes to build the MST

C. The min function call is incorrect

D. The visited set is never updated

Solution

1. Step 1: Analyze the code's MST construction

   The code updates keys but does not store which vertex connects to which, so MST edges are unknown.

2. Step 2: Identify missing MST parent tracking

   Prim's algorithm requires tracking parent nodes to reconstruct the MST edges, which is missing here.

3. Final Answer:

   The algorithm does not track parent nodes to build the MST -> Option B

4. Quick Check:

   Missing parent tracking = MST incomplete [OK]

Hint: Track parents to know MST edges, not just weights [OK]

Common Mistakes:

• Assuming keys alone build MST
• Ignoring parent node tracking
• Thinking visited set is not updated

5. You have a graph with vertices representing cities and edges representing roads with costs. If some roads have zero cost, how does Prim's algorithm handle these edges when building the minimum spanning tree?

hard

A. It always includes zero-cost edges first, possibly creating multiple disconnected trees

B. It causes an error because zero-cost edges are invalid

C. It ignores zero-cost edges because they don't reduce total cost

D. It treats zero-cost edges as the cheapest and includes them first to connect vertices

Solution

1. Step 1: Understand edge weight role in Prim's

   Prim's algorithm always picks the edge with the smallest weight connecting new vertices.

2. Step 2: Consider zero-cost edges

   Zero-cost edges are the cheapest possible, so they will be chosen first to connect vertices without increasing total cost.

3. Step 3: Confirm no errors or ignoring

   Zero-cost edges are valid and included; they do not cause errors or get ignored.

4. Final Answer:

   It treats zero-cost edges as the cheapest and includes them first to connect vertices -> Option D

5. Quick Check:

   Zero-cost edges = chosen first [OK]

Hint: Zero-cost edges are cheapest, so Prim picks them first [OK]

Common Mistakes:

• Thinking zero-cost edges cause errors
• Assuming zero-cost edges are ignored
• Believing zero-cost edges create disconnected trees