MST theory
EasyConnect every node for the least total weight
Problem
Learn the minimum spanning tree: a lowest-total-weight set of edges connecting all nodes without cycles.
Connect everything as cheaply as possible with no wasted loops.
The idea
A Minimum Spanning Tree links all V nodes using V-1 edges with the smallest possible total weight and no cycles. The animation grows one from a start node (Prim's method): at every step it takes the cheapest edge that reaches a node not yet in the tree. That greedy pick is always safe — the cheapest edge crossing any 'cut' must belong to some MST.
Step 1 of 10. A Minimum Spanning Tree connects every node with the least total edge weight. Start the tree with just A. tree A, weight 0.
1tree = {start}; total = 02min-heap of edges leaving the tree3repeat until tree has all nodes:4 pick the cheapest edge to a NEW node; add that node; total += weight5return total // minimum spanning tree weightInput
- nodes
- 5, 7 edges
Memory
- tree
- A
- add edge
- —
Output
- weight
- 0
- MST weight
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- weighted graph
- Output:
- MST edges
Finished the walkthrough? Add it to your streak.