Kruskal's MST Algorithm

Overview

Kruskal's algorithm is a popular method for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. It follows a greedy approach to find the MST by adding edges in increasing order of their weights.

Steps of Kruskal's Algorithm

• Sort all the edges in non-decreasing order of their weight.
• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include this edge. Else, discard it.
• Repeat step 2 until there are (V-1) edges in the spanning tree.

Example 1: Simple Graph

Consider a graph with vertices A, B, C, and D and edges with weights:

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

The MST will include edges A-B, A-D, and C-D.

Example 2: Dense Graph

In a dense graph with many edges, Kruskal's algorithm efficiently finds the MST by sorting edges and using union-find to detect cycles.

Edges: A-B (2), B-C (3), C-D (1), D-A (4), A-C (5), B-D (6)
            

The MST will include edges C-D, A-B, and B-C.

Example 3: Sparse Graph

For a sparse graph, Kruskal's algorithm is particularly useful because it only considers the essential edges.

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

The MST will include edges A-B and C-D.

Example 4: Graph with Equal Weights

When multiple edges have the same weight, Kruskal's algorithm can choose any of them as long as the cycle condition is not violated.

Edges: A-B (1), B-C (1), C-D (1), D-A (1)
            

The MST can include any three of these edges without forming a cycle.

Example 5: Disconnected Graph

Kruskal's algorithm can be applied to each connected component separately to find the MST of each component.

Component 1: A-B (2), B-C (3)
Component 2: D-E (1), E-F (4)
            

The MST of Component 1 includes A-B and B-C, while Component 2 includes D-E.