Kruskal’s Algorithm
Kruskal’s algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm that in each step adds to the forest to the lowest-weight edge that will not form a cycle.
This algorithm has a similar effect to Prim’s Algorithm, but it is different in the following ways:
- Kruskal’s starts by the edges. It takes all edges, sorts them in increasing order, and then iterates over the edges, checking along the way to make sure they don’t form a cycle, until a spanning tree is made.
Time Complexity
Kruskal is of time complexity O(E log E) or O(E log V), equivalently.