Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected, weighted graph. The algorithm sorts edges by weight and iteratively adds the smallest weight edge that does not create a cycle.

The algorithm performs the following steps:

• Create a disjoint set initially consisting of a separate single-vertex tree for each vertex in the input graph.
• Sort the graph edges by weight.
• Loop through the edges of the graph, in ascending sorted order by their weight. For each edge:
  • Test whether adding the edge to the current disjoint set would create a cycle.
  • If not, add the edge to the disjoint set, unionizing two trees into a single tree.

Usage

Kruskal's algorithm is particularly effective for sparse graphs where the number of edges is much smaller than . The algorithm's edge-based approach makes it naturally parallelizable, as independent edges can be processed simultaneously.

When to use Kruskal's:

• Graphs with few edges relative to vertices
• When edges are already sorted or can be efficiently sorted
• When implementing parallel or distributed algorithms
• Network design problems with linear cost structures

Analysis

Looking at the main operations in Kruskal's algorithm:

1. Sorting edges: The algorithm sorts all edges by weight using a comparison-based sort, which takes time.
2. Processing edges: For each edge, the algorithm performs a find operation (twice) and possibly a unionSets operation on the union-find data structure.

With path compression and union by rank optimizations, each union-find operation takes amortized time, where is the inverse Ackermann function. For all practical purposes, .

Processing all edges thus takes time, which is nearly linear.

Combining these operations:

Since for simple graphs, we have , so: