Kruskal's Algorithm

Kruskal's Algorithm is another way to find a Minimum Spanning Tree (MST) in a graph. It works by iteratively adding the cheapest available edge that connects two previously disconnected components, without forming a cycle. It is efficient for sparse graphs and uses a union-find data structure to detect cycles.

Step by Step

• Sort all edges in non-decreasing order of their weights.
• Initialize a Disjoint-set structure with each vertex in its own set (component).
• For each edge (u, v) in the sorted list:
  • Use Find operation to determine the sets of u and v.
  • If the sets are different, the edge does not form a cycle. Add it to the MST.
  • Merge the two sets using Union operation.
• Repeat until the MST contains V-1 edges.

Things to Observe

• Component Merging: Observe how adding an edge merges two previously separate components into one. The visualization shows nodes moving together as components are unified, demonstrating how the algorithm gradually connects all vertices.
• Cycle Detection: Watch how union-find data structure efficiently checks if two vertices are not in the same connected component before adding an edge.