Kruskal's MST Simulator
Sort every edge, then add the ones that do not close a cycle — union-find included.
Sort every edge by weight: E-F=1, A-D=2, C-F=2, B-E=3, F-H=3, A-B=4, G-H=4, D-E=5, B-C=6, E-G=7, D-G=8. Each node starts as its own component.
step 1 of 13
expanding nowinspectingin frontierdone / in treeuntouched
Kruskal's Algorithm
Sorts every edge by weight and takes each one that joins two different components, using union-find to detect cycles.
- Time
- O(E log E)
Edges by weight
E-F (1)A-D (2)C-F (2)B-E (3)F-H (3)A-B (4)G-H (4)D-E (5)B-C (6)E-G (7)D-G (8)
Highlighted entry comes out next.
- Edges chosen
- 0
- Total weight
- 0
Build your graph
—
Edges (11)
- A — B(4)
- A — D(2)
- B — C(6)
- B — E(3)
- C — F(2)
- D — E(5)
- D — G(8)
- E — F(1)
- E — G(7)
- F — H(3)
- G — H(4)
← → to step, or use the buttons above.