Introduction
Prerequisites: Graph Theory
A spanning tree of a graph is a tree that spans all the nodes of the graph but only using some of the edges to connect all the nodes.
A minimum spanning tree is the spanning tree that requires the minimum of some property such as total weight or total edges.
Spanning tree algorithms are essential in networking to ensure no loops occur when sending data through a network.
Implementations
| Algorithm | Desc | Time | Space |
|---|---|---|---|
| Prim's | Using greedy method | O(n log n) | O(n2) |
| Kruskal | Using connected components | O(n log n) | O(n2) |
Exercises
- Given a weighted graph with N nodes, find the smallest total cost to connect all nodes into 3 separate groups. (A single node can be a group)
- Same as 3, but a group must contain at least 3 other nodes.