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

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

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

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

Hint

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

Practice

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

easy

A. To detect if a graph contains cycles

B. To find the shortest path between two vertices

C. To find the minimum spanning tree connecting all vertices without cycles

D. To sort vertices by their degree

Solution

1. Step 1: Understand the purpose of Kruskal's algorithm

   Kruskal's algorithm is designed to connect all points in a graph with the smallest total edge weight without forming any loops.

2. Step 2: Compare with other graph problems

   Unlike shortest path or cycle detection alone, Kruskal's focuses on building a minimum spanning tree, which is a tree connecting all vertices with minimal cost.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices without cycles -> Option C

4. Quick Check:

   Kruskal's goal = minimum spanning tree [OK]

Hint: Kruskal's connects all points cheaply without loops [OK]

Common Mistakes:

• Confusing minimum spanning tree with shortest path
• Thinking it detects cycles only
• Assuming it sorts vertices instead of edges

2. Which of the following is the correct first step in Kruskal's algorithm?

easy

A. Pick any vertex and start a depth-first search

B. Sort all edges in increasing order of their weights

C. Remove all vertices with degree 1

D. Sort vertices by their labels alphabetically

Solution

1. Step 1: Identify the initial step of Kruskal's algorithm

   Kruskal's algorithm begins by sorting all edges by their weight from smallest to largest to ensure the cheapest edges are considered first.

2. Step 2: Eliminate incorrect options

   Depth-first search and vertex removal are not part of Kruskal's initial steps, and sorting vertices alphabetically is irrelevant.

3. Final Answer:

   Sort all edges in increasing order of their weights -> Option B

4. Quick Check:

   First step = sort edges by weight [OK]

Hint: Always start by sorting edges by weight ascending [OK]

Common Mistakes:

• Sorting vertices instead of edges
• Starting with a search instead of sorting
• Removing vertices prematurely

3. Given the edges with weights: (A-B: 1), (B-C: 4), (A-C: 3), (C-D: 2), what edges will Kruskal's algorithm select for the minimum spanning tree?

medium

A. (A-C), (B-C), (C-D)

B. (A-B), (C-D), (B-C)

C. (A-B), (C-D), (A-C), (B-C)

D. (A-B), (C-D), (A-C)

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (A-B:1), (C-D:2), (A-C:3), (B-C:4).

2. Step 2: Add edges without creating cycles

   Add (A-B), then (C-D). Adding (A-C) connects A and C without cycle. Adding (B-C) would create a cycle, so skip it.

3. Final Answer:

   (A-B), (C-D), (A-C) -> Option D

4. Quick Check:

   Edges chosen = smallest weights without cycles [OK]

Hint: Pick edges from smallest weight, skip if cycle forms [OK]

Common Mistakes:

• Including all edges regardless of cycles
• Choosing heavier edges before lighter ones
• Not checking for cycles before adding edges

4. In Kruskal's algorithm, what is the common error if the algorithm adds an edge that creates a cycle?

medium

A. The disjoint set structure is not used or updated correctly

B. Edges are not sorted by weight

C. Vertices are not labeled properly

D. The graph is directed instead of undirected

Solution

1. Step 1: Understand cycle prevention in Kruskal's

   Kruskal's algorithm uses a disjoint set (union-find) data structure to track connected components and avoid cycles.

2. Step 2: Identify the cause of cycle creation

   If an edge creates a cycle, it means the disjoint set was not used or updated properly to detect that the two vertices are already connected.

3. Final Answer:

   The disjoint set structure is not used or updated correctly -> Option A

4. Quick Check:

   Cycle error = faulty disjoint set use [OK]

Hint: Use disjoint sets to detect cycles before adding edges [OK]

Common Mistakes:

• Ignoring disjoint set updates
• Assuming sorting fixes cycles
• Confusing graph direction with cycle detection

5. You have a graph with edges: (X-Y: 2), (Y-Z: 2), (X-Z: 3), (Z-W: 1), (W-X: 4). Using Kruskal's algorithm, which set of edges forms the minimum spanning tree?

hard

A. (Z-W), (X-Y), (Y-Z)

B. (X-Y), (Y-Z), (X-Z)

C. (Z-W), (X-Z), (W-X)

D. (Z-W), (X-Y), (Y-Z), (W-X)

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (Z-W:1), (X-Y:2), (Y-Z:2), (X-Z:3), (W-X:4).

2. Step 2: Add edges without cycles until all vertices connected

   Add (Z-W), then (X-Y), then (Y-Z). Now all vertices X, Y, Z, W are connected. Adding (W-X) or (X-Z) would create cycles, so skip them.

3. Final Answer:

   (Z-W), (X-Y), (Y-Z) -> Option A

4. Quick Check:

   Minimum spanning tree = edges with smallest weights connecting all nodes [OK]

Hint: Add smallest edges until all vertices connected, avoid cycles [OK]

Common Mistakes:

• Adding extra edges causing cycles
• Skipping necessary edges to connect all vertices
• Choosing heavier edges before lighter ones