Kruskal's algorithm

Kruskal's algorithm is a greedy algorithm that tries to find a Minimum Spanning Tree among a graph. To achieve this, he use a minimal spanning forest first and connect the trees together.

It works well for less dense graph.


Its behaviour is similar to Prim's algorithm, but it uses multiple trees before connecting them together.

Algorithm

• Create a forest (a set of trees) 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 forest would create a cycle
  • If not, add the edge to the forest, combining two trees into a single tree

Complexity

Kruskal algorithm has a time complexity of $O(|E|\log |V|)$

Resources

• Kruskal's algorithm visualization - David Galles