Minimum spanning tree (Prim's) in Data Structures Theory - Mini Project: Build & Apply

Minimum Spanning Tree using Prim's Algorithm

📖 Scenario: You are working with a small network of cities connected by roads. Each road has a cost to maintain. You want to find the cheapest way to connect all cities so that there is a path between any two cities without any loops.

🎯 Goal: Build a step-by-step representation of Prim's algorithm to find the minimum spanning tree (MST) of a weighted graph representing cities and roads.

📋 What You'll Learn

Create a graph data structure with cities as nodes and roads with costs as edges

Set up a starting city for Prim's algorithm

Implement the core logic to select the next edge with the smallest cost connecting to the MST

Complete the MST by adding all cities with minimum total cost without cycles

💡 Why This Matters

🌍 Real World

Prim's algorithm helps in designing efficient networks like roads, electrical grids, or computer networks by minimizing the total connection cost.

💼 Career

Understanding minimum spanning trees is important for roles in network design, operations research, and software engineering where optimization of resources is needed.

1

Create the graph data structure

Create a dictionary called graph representing the cities and roads. Use the exact keys and values: 'A': {'B': 2, 'C': 3}, 'B': {'A': 2, 'C': 1, 'D': 4}, 'C': {'A': 3, 'B': 1, 'D': 5}, 'D': {'B': 4, 'C': 5}.

Data Structures Theory

# Create the graph dictionary with the given cities and road costs
# Your code here

Hint

Use a dictionary where each city points to another dictionary of connected cities and their road costs.

2

Set the starting city and initialize MST variables

Create a variable called start_city and set it to 'A'. Also create a set called visited containing only start_city. Create a list called edges that will hold tuples of the form (cost, from_city, to_city).

Data Structures Theory

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}
}
# Set the starting city and initialize visited set and edges list
# Your code here

Hint

Start from city 'A'. Keep track of visited cities in a set. Prepare an empty list for edges to explore.

3

Add edges from the starting city to the edges list

Use a for loop with variables to_city and cost to iterate over graph[start_city].items(). Inside the loop, append tuples of the form (cost, start_city, to_city) to the edges list.

Data Structures Theory

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}
}
start_city = 'A'
visited = {start_city}
edges = []
# Add edges from start_city to edges list
# Your code here

Hint

Loop over neighbors of 'A' and add their edges with costs to the edges list.

4

Complete the MST by selecting edges with minimum cost

Use a while loop that runs while len(visited) < len(graph). Inside, find the edge with the smallest cost in edges where the to_city is not in visited. Add the to_city to visited. Then add all edges from this new city to edges if the connected city is not visited. Use variables cost, from_city, and to_city for unpacking edges.

Data Structures Theory

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}
}
start_city = 'A'
visited = {start_city}
edges = []
for to_city, cost in graph[start_city].items():
    edges.append((cost, start_city, to_city))
# Complete the MST by selecting edges with minimum cost
# Your code here

Hint

Keep picking the smallest edge that connects to a new city and add its edges to explore next.

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