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

Need a 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

Need a 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

Need a 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

Need a hint?

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