Kruskal’s Algorithm

Goal

Our goal is to find the minimum spanning tree (MST) from the graph, which satisfies:

• All the nodes are connected.
• The sum of weights is minimized.

Idea

The key ideas for the Kruskal’s algorithm are:

1. Greedy approach: we always process the edge with smallest weight first.
   • Sort the edges in ascending order before processing.
2. Exclude redundant edges: if adding the edge forms a cycle, skip it.
   • Use union-find algorithm to check if an edge forms a cycle.
3. Early stopping: we only need N-1 edges for N nodes.
   • This avoids redundant checks in large graphs.

Code

n = 4
edges = [(10, 1, 2),
         (30, 1, 3),
         (20, 2, 3),
         (40, 2, 4),
         (50, 3, 4),]

parent = [0, 1, 2, 3, 4]
mst = []

# Greedy approach: always process the smallest edge first.
edges.sort(key=lambda x: x[0])

def find_root(x):
    if parent[x] != x:
        parent[x] = find_root(parent[x])
    return parent[x]

def union(x, y):
    root_x = find_root(x)
    root_y = find_root(y)
    if root_x != root_y:
        parent[root_y] = root_x
        return True 
    else:
        return False # Cycle detected

# Check edges if they form a cycle
for edge in edges:
    if len(mst) == n - 1:
        break  # Early stopping
    x = edge[1]
    y = edge[2]
    if union(x, y):
        mst.append(edge)
    else:
        continue # Skip this edge since a cycle detected

print(mst)