Lesson 6 of 11Article16 min
Trees, Spanning Trees & Shortest Paths
Trees, Spanning Trees & Shortest Paths
Acyclic connected structure
- Rooted trees: parent/child; binary trees; traversal orders.
- MST: Kruskal / Prim — connect all vertices at minimum total weight.
- Shortest paths: BFS unweighted; Dijkstra non-negative weights.
- Union-Find powers Kruskal's efficiency.
Many "optimisation on networks" problems reduce to spanning trees or shortest paths — recognise the pattern.