Minimum spanning tree (Kruskal's) in Data Structures Theory - Full Explanation

Introduction

Imagine you want to connect several cities with roads so that every city is reachable from any other city, but you want to spend the least amount of money building these roads. Finding the cheapest way to connect all points without any loops is the problem that minimum spanning trees solve. Kruskal's algorithm is one way to find this cheapest connection.

Explanation

Graph and edges

A graph is a collection of points called vertices connected by lines called edges. Each edge has a cost or weight that represents how expensive it is to use or build that connection. Kruskal's algorithm works by looking at all these edges and deciding which ones to include.

Kruskal's algorithm starts by considering all edges sorted by their cost.

Sorting edges by weight

The first step in Kruskal's algorithm is to sort all edges from the smallest cost to the largest. This way, the algorithm can pick the cheapest connections first to build the minimum spanning tree. Sorting helps ensure the total cost stays as low as possible.

Sorting edges by weight ensures the algorithm always picks the cheapest available connection.

Building the tree without cycles

Kruskal's algorithm adds edges one by one from the sorted list, but only if adding that edge does not create a loop or cycle. This keeps the structure a tree, meaning all points are connected with no closed loops. To check this, the algorithm uses a method to track which points are already connected.

Edges are added only if they connect two separate groups, avoiding cycles.

Union-Find data structure

To efficiently check if adding an edge creates a cycle, Kruskal's algorithm uses a Union-Find structure. This keeps track of which vertices are connected in groups. When an edge connects two different groups, they are merged. If they are already in the same group, adding that edge would create a cycle and is skipped.

Union-Find helps quickly decide if two vertices belong to the same connected group.

Resulting minimum spanning tree

After processing all edges, the selected edges form a tree that connects all vertices with the smallest total cost. This tree is called the minimum spanning tree. It ensures every point is reachable without any unnecessary or expensive connections.

The final set of edges connects all points with the minimum total cost and no cycles.

Real World Analogy

Imagine you are building a network of roads to connect several villages. You want to use the least amount of road material possible, so you start by building the shortest roads first. But you avoid building roads that would create loops, because loops waste materials. You keep adding roads until all villages are connected.

Graph and edges → Villages as points and possible roads as connections between them

Sorting edges by weight → Choosing to build the shortest roads first to save materials

Building the tree without cycles → Avoiding building roads that create loops to prevent waste

Union-Find data structure → Keeping track of which villages are already connected by roads

Resulting minimum spanning tree → A network of roads connecting all villages with minimum total length

Diagram

Diagram

Vertices: A, B, C, D, E

Edges sorted by weight:
  A-B (1)
  B-C (2)
  A-C (3)
  C-D (4)
  D-E (5)

Process:
  Start with empty tree
  ┌─────────────┐
  │ Add A-B (1) │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Add B-C (2) │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Skip A-C (3)│ (creates cycle)
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Add C-D (4) │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Add D-E (5) │
  └─────────────┘

Final MST edges: A-B, B-C, C-D, D-E

This diagram shows the step-by-step selection of edges by Kruskal's algorithm to build the minimum spanning tree without cycles.

Key Facts

Minimum Spanning Tree → A tree connecting all vertices with the smallest possible total edge weight and no cycles.

Kruskal's Algorithm → An algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, skipping those that create cycles.

Union-Find → A data structure used to track and merge connected components efficiently to avoid cycles.

Cycle → A path in a graph that starts and ends at the same vertex without repeating edges.

Edge Weight → A value representing the cost or distance associated with an edge in a graph.

Code Example

Data Structures Theory

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

def kruskal(n, edges):
    uf = UnionFind(n)
    mst = []
    edges.sort(key=lambda x: x[2])  # sort by weight
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst

# Example graph with 5 vertices (0 to 4)
edges = [
    (0, 1, 1),
    (1, 2, 2),
    (0, 2, 3),
    (2, 3, 4),
    (3, 4, 5)
]
result = kruskal(5, edges)
for edge in result:
    print(edge)

Common Confusions

Believing Kruskal's algorithm always picks edges connected to a single starting vertex.

Believing Kruskal's algorithm always picks edges connected to a single starting vertex. Kruskal's algorithm considers all edges globally sorted by weight and connects any two separate groups, not just edges from one vertex.

Thinking cycles are allowed in the minimum spanning tree.

Thinking cycles are allowed in the minimum spanning tree. A minimum spanning tree must never contain cycles because it must be a tree connecting all vertices with no loops.

Assuming the algorithm stops after connecting some vertices.

Assuming the algorithm stops after connecting some vertices. Kruskal's algorithm continues until all vertices are connected in one spanning tree.

Summary

Kruskal's algorithm finds the cheapest way to connect all points by adding edges from smallest to largest weight without creating loops.

It uses a Union-Find structure to efficiently check if adding an edge would create a cycle.

The result is a minimum spanning tree that connects all vertices with the lowest total cost.

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