Spanning Tree Algorithm
1. Introduction
In graph theory and computer science, a spanning tree is a fundamental concept used in
network design, routing, optimization, and distributed systems. Given a connected graph, a
spanning tree connects all the vertices together without forming any cycles, using the minimum
possible number of edges.
A spanning tree algorithm is used to find such a tree efficiently. These algorithms play a
crucial role in:
• Computer networks (loop-free topology)
• Minimum cost network design
• Distributed systems
• Broadcasting and routing
2. Basic Concepts and Definitions
2.1 Graph
A graph is defined as:
• G = (V, E)
where
o V = set of vertices (nodes)
o E = set of edges (links)
Graphs can be:
• Directed or undirected
• Weighted or unweighted
• Connected or disconnected
2.2 Tree
A tree is a connected, acyclic graph.
Properties:
• Contains no cycles
• Has exactly |V| − 1 edges
• There is exactly one path between any two vertices
2.3 Spanning Tree
A spanning tree of a graph G is a subgraph that:
1. Includes all vertices
2. Is connected
3. Has no cycles
A graph can have multiple spanning trees.
2.4 Minimum Spanning Tree (MST)
If the graph is weighted, a Minimum Spanning Tree (MST) is a spanning tree whose total edge
weight is minimum.
3. Importance of Spanning Tree Algorithms
Spanning tree algorithms are important because they:
• Minimize redundancy in networks
• Eliminate routing loops
• Reduce cost in network design
• Ensure efficient data broadcasting
• Form the basis of routing and switching protocols
4. Characteristics of Spanning Trees
• Number of edges = V − 1
• No cycles
• Removal of any edge disconnects the tree
• Adding any edge creates a cycle
• All nodes are reachable from each other
5. Types of Spanning Tree Algorithms
There are two main categories:
1. Minimum Spanning Tree Algorithms
2. Distributed Spanning Tree Algorithms
6. Minimum Spanning Tree Algorithms
6.1 Prim’s Algorithm
6.1.1 Overview
Prim’s algorithm builds the MST by:
• Starting from any vertex
• Expanding the tree by adding the minimum-weight edge that connects a vertex inside
the tree to one outside
6.1.2 Algorithm Steps
1. Choose an arbitrary starting vertex
2. Initialize MST as empty
3. Add the minimum weight edge connecting the tree to a new vertex
4. Repeat until all vertices are included
6.1.3 Example
Given a weighted graph:
• Start from vertex A
• Choose smallest adjacent edge
• Add vertices incrementally
6.1.4 Time Complexity
• Using adjacency matrix: O(V²)
• Using priority queue (binary heap): O(E log V)
6.1.5 Advantages
• Efficient for dense graphs
• Simple to implement
6.2 Kruskal’s Algorithm
6.2.1 Overview
Kruskal’s algorithm:
• Sorts all edges by increasing weight
• Adds edges one by one
• Skips edges that form cycles
6.2.2 Algorithm Steps
1. Sort edges in ascending order
2. Initialize each vertex as a separate set
3. Add smallest edge that does not form a cycle
4. Repeat until MST has V − 1 edges
6.2.3 Cycle Detection
• Uses Disjoint Set (Union-Find) data structure
6.2.4 Time Complexity
• Sorting edges: O(E log E)
• Union-Find operations: near constant time
6.2.5 Advantages
• Efficient for sparse graphs
• Easy to understand
6.3 Borůvka’s Algorithm
6.3.1 Overview
Borůvka’s algorithm:
• Each component selects the cheapest outgoing edge
• Components merge until one tree remains
6.3.2 Characteristics
• Parallelizable
• Efficient for large distributed systems
7. Comparison of MST Algorithms
Algorithm Approach Best for Time Complexity
Prim’s Vertex-based Dense graphs O(E log V)
Kruskal’s Edge-based Sparse graphs O(E log E)
Borůvka’s Component-based Distributed systems O(E log V)
8. Distributed Spanning Tree Algorithm (STP)
8.1 Need for STP in Networks
In computer networks, especially Ethernet LANs, loops can cause:
• Broadcast storms
• Duplicate frames
• MAC table instability
To avoid this, Spanning Tree Protocol (STP) is used.
8.2 Spanning Tree Protocol (IEEE 802.1D)
STP dynamically builds a loop-free logical topology.
8.2.1 Key Concepts
• Bridge ID (BID)
• Root Bridge
• Root Port
• Designated Port
• Blocked Port
8.2.2 STP Algorithm Steps
1. Elect the Root Bridge
2. Determine shortest path to root
3. Select root and designated ports
4. Block redundant links
8.2.3 Port States
• Blocking
• Listening
• Learning
• Forwarding
• Disabled
9. Applications of Spanning Tree Algorithms
• Network topology design
• Routing algorithms
• Broadcast systems
• Cluster analysis
• VLSI design
• Power grids and road networks
• Database query optimization
10. Advantages of Spanning Tree Algorithms
• Ensures loop-free networks
• Reduces redundancy
• Minimizes cost
• Improves network efficiency
• Simplifies routing
11. Limitations
• Single path between nodes (no redundancy)
• Recalculation needed if topology changes
• STP convergence time can be slow
12. Enhancements and Variants
• Rapid Spanning Tree Protocol (RSTP – 802.1w)
• Multiple Spanning Tree Protocol (MSTP – 802.1s)
• Shortest Path Bridging (SPB)
13. Conclusion
The Spanning Tree Algorithm is a cornerstone of graph theory and network design. By
ensuring connectivity without cycles, it enables efficient communication, optimal resource
utilization, and stable network operation. From Minimum Spanning Tree algorithms like
Prim’s and Kruskal’s to distributed spanning tree protocols in networking, these algorithms
are indispensable in both theoretical and practical computing environments.