Seth.

Overview

Kruskal's Algorithm is used to find the Minimum Spanning Tree (MST) of a connected, undirected graph. The MST is a subgraph that connects all vertices with the smallest total edge weight without forming any cycles.

Steps of Kruskal's Algorithm

1. Sort all edges by their weight in ascending order.
2. Initialize a Disjoint Set to track connected components.
3. For each edge, add it to the MST if it doesn’t form a cycle, using the Union-Find structure.
4. Stop when you have added V-1 edges (for V vertices).

Example

Consider the following graph:

Sorted edges: (1-2: 1), (1-3: 2), (3-4: 2), (0-2: 3), (0-1: 4), (2-3: 4), (4-5: 6)

Steps:

• Add edge (1-2: 1) → Connects vertices 1 and 2.
• Add edge (1-3: 2) → Connects vertices 1 and 3.
• Add edge (3-4: 2) → Connects vertices 3 and 4.
• Add edge (0-2: 3) → Connects vertices 0 and 2.
• Add edge (4-5: 6) → Connects vertices 4 and 5.

Now, the MST is complete with 5 edges.

Time Complexity

The time complexity is O(E log E) due to sorting the edges, where E is the number of edges.

Use Cases

Kruskal’s algorithm is useful for designing networks like telecommunication systems or transportation grids.