Graph Algorithms • MST

Kruskal's Algorithm

A greedy algorithm that finds the Minimum Spanning Tree by sorting all edges and adding them if they don't form a cycle. It's a forest-growing approach using Disjoint Set Union.

Try Interactive Simulator

Step 1: Sort

Begin by sorting all edges of the graph in non-decreasing order of their weight.

Step 2: Greed

Pick the smallest edge. Check if adding it forms a cycle with the spanning tree formed so far.

Step 3: Cycle Check

Use Disjoint Set Union (DSU) to check if nodes are in the same component. If they aren't, add the edge!

Termination

Repeat until there are (V-1) edges in the MST, where V is the number of vertices.

Loading Lab...

Graph Algorithms • MST

Kruskal's Algorithm

A greedy algorithm that finds the Minimum Spanning Tree by sorting all edges and adding them if they don't form a cycle. It's a forest-growing approach using Disjoint Set Union.

Try Interactive Simulator

Step 1: Sort

Begin by sorting all edges of the graph in non-decreasing order of their weight.

Step 2: Greed

Pick the smallest edge. Check if adding it forms a cycle with the spanning tree formed so far.

Step 3: Cycle Check

Use Disjoint Set Union (DSU) to check if nodes are in the same component. If they aren't, add the edge!

Termination

Repeat until there are (V-1) edges in the MST, where V is the number of vertices.

Mst Kruskal

Mst Kruskal

Kruskal's Algorithm

Step 1: Sort

Step 2: Greed

Step 3: Cycle Check

Termination

Kruskal's Algorithm

Step 1: Sort

Step 2: Greed

Step 3: Cycle Check

Termination