Kruskal's Algorithm
- Tags
- algorithm
Is an algorithm to find the minimum spanning tree of a graph \( G \).
Formulation
The algorithm is:
- Sort the edges into ascending order.
- Choose an edge with the minimum weight and join on a sub-graph.
- Find the next edge of minimum weight that does not make cycle and add that to the sub-graph.
- Repeat step 3 until all vertices are connected.