What Is a Spanning Tree in Graph Theory?
A spanning tree is a subgraph of a connected, undirected graph that:
- Includes all the vertices of the original graph.
- Is connected.
- Contains no cycles.
If a graph has V vertices, its spanning tree contains exactly V − 1 edges. Therefore, a spanning tree connects every vertex of the original graph without forming a cycle.
Why Do We Need a Spanning Tree?
A graph may contain many vertices and edges. Sometimes, we do not need every edge to keep all the vertices connected.
A spanning tree helps us:
- Connect all vertices without cycles.
- Remove unnecessary edges while maintaining connectivity.
- Understand network structures.
- Design cost-efficient networks using Minimum Spanning Trees.
For example, when connecting computers in a laboratory, we may have several possible connections. A spanning tree identifies a set of connections that keeps all computers connected without creating cycles.
How Is a Spanning Tree Formed? (Example)
Let us consider a connected graph containing four vertices: A, B, C and D, with the edges AB, AC, BC, BD and CD.
Original graph
Our aim is to connect all four vertices without forming any cycle.
Step 1: Remove Edge BC
After removing BC, the remaining edges are AB, AC, BD and CD.
Edge BC removed (dashed red)
All vertices remain connected, but a cycle still exists: A → B → D → C → A.
Step 2: Remove Another Edge
Remove edge CD.
Spanning tree (green): AB, AC and BD
The remaining edges are AB, AC and BD. Now, all four vertices are connected, no cycle exists, and the graph contains exactly three edges.
Therefore, the resulting graph is a spanning tree.
Number of Spanning Trees in a Graph
A connected graph may have multiple spanning trees. The exact number depends on the graph’s structure.
For example, the graph with vertices A, B, C and D and edges AB, AC, BC, BD and CD has 8 possible spanning trees.
For a complete graph, the number of possible spanning trees is calculated using Cayley’s formula for spanning trees:
Number of spanning trees of a complete graph = nn−2
Here, Kn represents a complete graph with n labelled vertices.
For example, K4 has: 44−2 = 42 = 16 spanning trees.
Properties of a Spanning Tree
Every spanning tree has the following important spanning tree properties.
Property 1: It Includes All Vertices
A spanning tree must contain every vertex of the original graph. If the original graph has vertices A, B, C and D, all four must appear in the spanning tree.
Property 2: It Is Connected
There must be a path between every pair of vertices. No vertex should be disconnected from the remaining graph.
Property 3: It Contains No Cycles
A spanning tree must be cycle-free. If a cycle exists, at least one edge can be removed from that cycle without disconnecting the graph.
Property 4: It Contains Exactly V − 1 Edges
The formula is:
Number of edges = V − 1
Here, V represents the number of vertices.
For example, if a graph contains six vertices, the number of edges in every spanning tree is: V − 1 = 6 − 1 = 5 edges.
Note: The original graph may contain many edges, but every spanning tree of that connected graph contains exactly V − 1 edges.
Also, removing any edge from a spanning tree disconnects it. This means every edge in the tree is necessary for maintaining connectivity.
What Is a Minimum Spanning Tree (MST)?
A Minimum Spanning Tree (MST) is a spanning tree of a connected, undirected, weighted graph that has the minimum possible total edge weight.
In simple words, an MST connects all vertices without cycles while minimizing the total cost of the selected edges.
Imagine that four cities must be connected using roads. Each possible road has a different construction cost. Our goal is to connect all four cities while spending as little as possible.
This is a typical application of a Minimum Spanning Tree.
Minimum Spanning Tree Example
Here, the weight may represent road construction cost or distance. Suppose the graph contains the following edges:
- BC with weight 1
- AC with weight 2
- CD with weight 3
- AB with weight 4
- BD with weight 5
Weighted graph
Step 1: Select Suitable Edges with Minimum Cost
Select BC (1), AC (2) and CD (3).
MST edges shown in green
Step 2: Check Connectivity
All four vertices A, B, C and D are connected. There is no cycle, and the tree contains exactly three edges.
Step 3: Calculate the Total Weight
Total weight = 1 + 2 + 3 = 6.
The MST minimizes the sum of the selected edge weights.
Note: An MST does not reduce the number of vertices or the required number of edges. Every spanning tree of the same connected graph has exactly V − 1 edges.
A graph may also have multiple MSTs when different spanning trees achieve the same minimum total weight.
Spanning Tree vs. Minimum Spanning Tree
Although the terms are related, a spanning tree and a Minimum Spanning Tree have different purposes.
| Feature | Spanning Tree | Minimum Spanning Tree |
|---|
| Meaning | Connects all vertices without cycles. | Connects all vertices without cycles at minimum total weight. |
| Edge weights | Not required. | Used to calculate total cost. |
| Number of edges | V − 1 | V − 1 |
| Connectivity | Connected | Connected |
| Cycles | Not allowed | Not allowed |
| Main objective | Maintain connectivity without cycles. | Minimize total edge weight. |
| Common algorithms | Select suitable edges while maintaining connectivity. | Prim’s and Kruskal’s algorithms. |
For example, suppose two spanning trees connect the same set of vertices. One has a total weight of 12, while the other has a total weight of 8.
Both may be valid spanning trees, but the second is the MST if 8 is the minimum achievable total weight.
Note: Every Minimum Spanning Tree is a spanning tree, but not every spanning tree is a Minimum Spanning Tree.
Spanning Tree Algorithms: How to Find a Minimum Spanning Tree
Two important minimum spanning tree algorithms are used to find an MST:
- Kruskal’s algorithm.
- Prim’s algorithm.
Both algorithms find an MST, but they follow different approaches.
A. Kruskal’s Algorithm in Data Structure
Kruskal’s algorithm finds a Minimum Spanning Tree by selecting edges in increasing order of weight while avoiding cycles.
Steps of Kruskal’s Algorithm
- List all the edges and their weights.
- Sort the edges in ascending order of weight.
- Select the next smallest edge that does not form a cycle. If an edge creates a cycle, reject it and consider the next edge.
- Continue until V − 1 edges have been selected.
Kruskal’s Algorithm Example
Consider the weighted graph described earlier. There are four vertices, so the MST must contain three edges.
Step 1: Sort the Edges in Ascending Order
| Order | Edge | Weight |
|---|
| 1 | BC | 1 |
| 2 | AC | 2 |
| 3 | CD | 3 |
| 4 | AB | 4 |
| 5 | BD | 5 |
Step 2: Select Minimum Edges One by One
| Edge considered | Decision | Reason |
|---|
| BC (1) | Select | No cycle |
| AC (2) | Select | No cycle |
| CD (3) | Select | No cycle; all vertices are connected |
Final MST from Kruskal’s algorithm
We have selected three edges, which is V − 1. Therefore, the algorithm stops.
The MST contains BC, AC and CD. Total weight = 1 + 2 + 3 = 6.
Important rule: Kruskal’s algorithm selects the smallest available edge that does not create a cycle. It commonly uses the Union-Find data structure for efficient cycle detection.
B. Prim’s Algorithm in Data Structure
Prim’s algorithm finds a Minimum Spanning Tree by starting from one vertex and gradually expanding the tree.
At every step, it selects the smallest-weight edge that connects a vertex already in the tree to a vertex outside the tree.
Steps of Prim’s Algorithm
- Start from any vertex.
- Find the smallest-weight edge connecting the current tree to an unselected vertex.
- Select that edge.
- Add the new vertex to the tree.
- Repeat until all vertices are included.
Prim’s Algorithm Example
Consider the same weighted graph.
Step 1: Start from Vertex A
The selected vertex is A.
Blue circles = vertices in the tree
Step 2: Choose the Smallest Available Edge
The available edges are AB (4) and AC (2). Choose AC (2). Selected vertices: A, C.
Step 3: Add the Next Vertex
The edges leading outside the tree are AB (4), BC (1) and CD (3). Choose BC (1). Selected vertices: A, B, C.
Step 4: Connect the Remaining Vertex D
The edges leading to the remaining vertex D are BD (5) and CD (3). Choose CD (3).
We have selected three edges, which is V − 1, and all vertices are connected. Therefore, the algorithm stops.
The selected MST edges are AC, BC and CD. Minimum total weight = 2 + 1 + 3 = 6.
Difference Between Prim’s and Kruskal’s Algorithm
Both algorithms produce a Minimum Spanning Tree, although their selection order may differ.
| Kruskal’s Algorithm | Prim’s Algorithm |
|---|
| Sorts and considers edges by increasing weight. | Starts from a vertex and grows a tree. |
| Selects an edge if it does not create a cycle. | Selects the minimum edge connecting the current tree to a new vertex. |
| May build separate components temporarily. | Maintains one growing tree. |
| Commonly uses Union-Find for cycle detection. | Commonly uses a priority queue for efficient edge selection. |
Both algorithms are widely used graph theory algorithms for solving Minimum Spanning Tree problems.
Real-Life Applications of Spanning Trees
Spanning trees and Minimum Spanning Trees are useful in many real-world applications.
1. Computer Networks
Computers, switches and other network devices may have multiple connections. In Ethernet networks, the Spanning Tree Protocol (STP) helps prevent switching loops by blocking selected redundant links while maintaining connectivity where possible.
2. Road Networks
Suppose several villages must be connected by roads. A spanning tree represents a cycle-free structure that connects every village. If road construction costs are known, an MST can help minimize the total construction cost.
3. Electrical Networks
Electrical distribution systems may require connections between several locations. An MST can help identify a low-cost connection structure when edge weights represent installation cost or wire length. Actual electrical designs must also satisfy safety, capacity and reliability requirements.
4. Communication Systems
Telephone towers, communication stations and network devices need connections to exchange information. Spanning trees help represent connectivity, while MSTs can help minimize connection costs.
5. Other Applications
Spanning trees are also used in cable network design, sensor networks, clustering algorithms, image processing and certain maze-generation techniques.
These examples show how graph theory can solve practical connectivity and optimization problems.
Conclusion
A spanning tree is a fundamental concept in data structures that helps us connect all vertices of a graph without cycles. It contains exactly V − 1 edges, and a connected graph may have multiple spanning trees.
When the edges have weights, the Minimum Spanning Tree helps us find a connection structure with the lowest possible total weight. Kruskal’s algorithm selects edges in increasing order of weight, while Prim’s algorithm grows a tree from a starting vertex.
Understanding spanning trees makes it easier to learn graph algorithms and their applications in computer networks, road construction, electrical networks and communication systems.
