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

Build a Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer tasked with connecting several computers with the least total cable length. You will use Kruskal's algorithm to find the minimum spanning tree (MST) of the network graph.

🎯 Goal: Build a step-by-step implementation of Kruskal's algorithm to find the minimum spanning tree of a weighted graph represented as a list of edges.

📋 What You'll Learn

Create a list of edges with exact weights and nodes

Create a helper structure to track connected components (disjoint sets)

Implement the core logic of Kruskal's algorithm to select edges

Complete the MST by collecting the selected edges

💡 Why This Matters

🌍 Real World

Network design, road construction, and other scenarios where connecting points with minimum total cost is needed.

💼 Career

Understanding MST algorithms is important for software engineers, network engineers, and data scientists working with optimization and graph problems.

1

Create the graph edges list

Create a list called edges containing these exact tuples representing edges and their weights: (1, 2, 4), (1, 3, 1), (2, 3, 3), (2, 4, 2), (3, 4, 5).

Data Structures Theory

# Create the list of edges with weights
# Your code here

Need a hint?

Use a list of tuples where each tuple has two nodes and the weight between them.

2

Create the disjoint set structure

Create a dictionary called parent where each node (1, 2, 3, 4) is its own parent initially, to track connected components.

Data Structures Theory

edges = [(1, 2, 4), (1, 3, 1), (2, 3, 3), (2, 4, 2), (3, 4, 5)]
# Create the parent dictionary for each node
# Your code here

Need a hint?

Each node is initially its own parent in the parent dictionary.

3

Implement the find and union functions

Define two functions: find(node) that returns the root parent of node using path compression, and union(node1, node2) that connects two nodes by setting the parent of one root to the other.

Data Structures Theory

edges = [(1, 2, 4), (1, 3, 1), (2, 3, 3), (2, 4, 2), (3, 4, 5)]
parent = {1: 1, 2: 2, 3: 3, 4: 4}
# Define find and union functions
# Your code here

Need a hint?

Use a loop in find to find the root parent and update parents for path compression. In union, connect roots if different.

4

Build the minimum spanning tree

Sort the edges by weight, create an empty list mst, then iterate over sorted edges. For each edge, if the roots of its nodes differ (use find), add the edge to mst and call union on the nodes.

Data Structures Theory

edges = [(1, 2, 4), (1, 3, 1), (2, 3, 3), (2, 4, 2), (3, 4, 5)]
parent = {1: 1, 2: 2, 3: 3, 4: 4}

def find(node):
    while parent[node] != node:
        parent[node] = parent[parent[node]]
        node = parent[node]
    return node

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)
    if root1 != root2:
        parent[root2] = root1

# Build the MST by selecting edges
# Your code here

Need a hint?

Sort edges by weight, then pick edges that connect different components until MST is complete.