Kruskal's Algorithm

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted, undirected, and connected graph. It works by iteratively adding the cheapest edge that connects two previously disconnected components, without forming a cycle.

Key Concepts

• Minimum Spanning Tree (MST): A tree that connects all vertices in a graph with the minimum possible total edge weight.
• Greedy Algorithm: An algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum.
• Disjoint Set Union (DSU) / Union-Find: A data structure used to efficiently keep track of the connected components and detect cycles.

Algorithm Steps

1. Sort Edges: Sort all the edges in the graph in non-decreasing order of their weights.
2. Initialize Disjoint Sets: Create a disjoint set for each vertex in the graph. Each vertex is initially in its own set.
3. Iterate Through Sorted Edges: Iterate through the sorted edges: a. For each edge (u, v) with weight w: i. Check if u and v are already in the same set using the find operation of DSU. ii. If they are not in the same set (i.e., adding this edge will not form a cycle): 1. Add the edge (u, v) to the MST. 2. Union the sets containing u and v using the union operation of DSU.
4. Termination: Continue until V-1 edges have been added to the MST (where V is the number of vertices), or all edges have been processed.

Time and Space Complexity

• Time Complexity: O(E log E) or O(E log V). Sorting edges takes O(E log E). The DSU operations (find and union) take nearly constant time on average (amortized O(α(V)), where α is the inverse Ackermann function, which is very slow-growing and practically constant). Since E can be at most V^2, log E is at most 2 log V, so O(E log E) is equivalent to O(E log V).
• Space Complexity: O(V + E) for storing the graph and the DSU structure.

Python Code Example

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

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1
            return True
        return False

def kruskals(vertices, edges):
    mst = []
    edges.sort(key=lambda x: x[2])  # Sort edges by weight
    ds = DisjointSet(vertices)

    for u, v, weight in edges:
        if ds.union(u, v):
            mst.append((u, v, weight))

    return mst

# Example Usage
vertices = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst_edges = kruskals(vertices, edges)
print("Edges in MST:", mst_edges)

total_weight = sum(edge[2] for edge in mst_edges)
print("Total weight of MST:", total_weight)