Definition
Kruskal's Algorithm
Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a undirected network.
For sparse graph, , Kruskal’s algorithm is better than Prim’s algorithm.
Runtime
- Union-find-operations are practically possible in constant time, i.e., the second part of the algorithm has nearly linear runtime.
- The total effort is now determined by edge sorting and is thus .