Kruskal's Algorithm
Minimum Spanning Tree
A minimum spanning tree is a crucial concept in graph theory with wide-ranging applications. Imagine a network represented as a graph, where vertices represent points (like cities or computers) and edges represent connections between them with associated costs (like distances or cable lengths). A spanning tree is a subgraph that connects all vertices without any cycles. A minimum spanning tree is a spanning tree with the lowest total edge weight. In essence, it’s the cheapest way to connect all points in the network, ensuring every point is reachable without redundant connections.
Kruskal's Algorithm
Kruskal’s algorithm is a greedy approach to finding an MST in a connected, undirected, weighted graph. The algorithm, as described in (Rayward‐Smith et al., 1991) and (Cormen et al., 2023), builds the MST by iteratively adding edges in increasing order of weight, ensuring no cycles are formed.
Algorithm:
- Initialization:
- Create a disjoint-set data structure where each vertex is initially in its own set. This represents a forest of individual, unconnected vertices.
- Sort all edges in the graph by weight in non-decreasing order.
- Iteration:
- For each edge (u, v) in sorted order:
- Find the sets to which vertices u and v belong using the FIND-SET operation of the disjoint-set data structure.
- If u and v belong to different sets (i.e., adding the edge wouldn’t create a cycle):
- Add edge (u, v) to the MST.
- Unite the sets containing u and v using the UNION operation, effectively merging the two connected components.
- For each edge (u, v) in sorted order:
- Termination: The algorithm terminates when all vertices are in the same set (i.e., the MST connects all vertices) or all edges have been considered.
Time Complexity: The complexity is dominated by the sorting of edges, which takes O(E log E) time, where E is the number of edges. Disjoint-set operations take nearly linear time, making the overall complexity O(E log E
