Kruskal's Algorithm (MST) Visualizer

Kruskal's Algorithm (MST)

sequentialRAM

A greedy Minimum Spanning Tree algorithm that sorts all graph edges by weight and repeatedly adds the lightest edge that does not form a cycle, using a Disjoint Set Union (DSU) data structure.

SIMULATION STEP PROGRESSStep 1 / 1

SPEED (50%)

Code Workspace

1procedure Kruskal(G)

2 MST := empty set

3 sort all edges E by weight ascending

4 makeSet(v) for each vertex v in G

5 for each edge (u, v) with weight w in sorted E do

6 if find(u) != find(v) then

7 add edge (u, v) to MST

8 union(u, v)

9 end if

10 end for

11end procedure

Currently highlights executing branch

RUNTIME COST METRICS

Comparisons0

Memory Writes0

Memory Reads0

Elements Swapped0

Computational Model:RAM (Single Core)

Theoretical Bound:O(E log E)

Space Complexity:O(V + E)

Communication Cost:0 (Shared Bus)

THEORETICAL ANALYSIS & RESEARCH

Conceptual Focus: A greedy Minimum Spanning Tree algorithm that sorts all graph edges by weight and repeatedly adds the lightest edge that does not form a cycle, using a Disjoint Set Union (DSU) data structure.

Real-world Industrial Applications:

Circuit layout and VLSI design
Cable TV network routing
Image segmentation and boundary detection