Spanning Tree (ST)
A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is also a tree (a connected acyclic graph).
The primary goal of a spanning tree is to connect all vertices with the minimum number of edges.
Uses of Spanning Tree:
- STs are used in network design and routing algorithms to ensure connectivity without cycles.
- They help identify bridges and critical connections in a network.
- Spanning trees are also used in data structures like Disjoint-Set Union (Union-Find) for efficient cycle detection.