Discrete Math › Section C · Graph theory › Topic C.3
Spanning trees
Given a network, which links can you drop and still reach every point? A spanning tree keeps every vertex connected with as few edges as possible, and when edges have costs, two simple greedy algorithms find the cheapest one.
In this topic
- Keeping everything connected, cheaply
- Every connected graph has one
- Worked example: counting spanning trees
- Spanning trees from searching
- Minimum spanning trees
- Kruskal's algorithm
- Worked example: Kruskal step by step
- Prim's algorithm
- Why being greedy is safe
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…