Spanning Trees and Their Significance
What is a Spanning Tree?
A spanning tree is a subgraph of a connected graph that:
Includes all the vertices (nodes) of the original graph.
Connects all the vertices together.
Has no cycles (loops).
Uses the minimum number of edges needed to connect all the vertices.
A spanning tree is the simplest way to connect every point in a graph without creating any loops.
Example
Original Graph
Edges:
AB
AC
BC
BD
CD
This graph contains cycles.
One Possible Spanning Tree
A
|
B
|
D
|
C
Edges:
AB
BD
DC
Notice that:
All four vertices are connected.
No loops exist.
It uses only 3 edges.
How Many Edges Does a Spanning Tree Have?
If a graph has n vertices, then every spanning tree has n−1 edges
Properties of a Spanning Tree
A spanning tree:
Connects all vertices.
Has no cycles.
Contains exactly n − 1 edges.
There is only one path between any two vertices.
Removing one edge disconnects the graph.
Adding one extra edge creates a cycle.
How to Find a Spanning Tree
Step 1: Start with the original connected graph.
Step 2: Include all vertices.
Step 3: Remove edges that create cycles.
Step 4: Stop when:
· All vertices remain connected.
· No cycles remain.
Example
Original graph
One spanning tree
A------B
|
|
C------D
Edges:
AB
AC
CD
There are 4 vertices, so a spanning tree has 3 edges.
Real-Life Examples of Spanning Trees
1. Internet Network
Suppose a company wants to connect several office computers.
Instead of installing unnecessary cables, it connects every computer using the minimum number of cables.
Benefit:
Saves money.
Eliminates unnecessary cable connections.
2. Road Construction
A government wants to connect several towns.
Instead of building every possible road, they build only enough roads so every town is reachable.
Benefit:
Lower construction cost.
Easy transportation.
3. Electrical Power Distribution
Electric companies connect houses to substations.
They avoid unnecessary wiring while ensuring every house receives electricity.
Benefit:
Less wiring.
Lower maintenance costs.
4. Water Supply System
A city installs water pipes to every neighborhood.
Only the necessary pipes are used to connect all areas.
Benefit:
Saves materials.
Easier repairs.
5. School Computer Laboratory
Twenty computers must all connect to a server.
Instead of connecting every computer to every other computer, only the required connections are used.
Benefit:
Reduced network traffic.
Lower installation cost.
Significance (Importance) of Spanning Trees
Spanning trees are important because they:
Minimize Cost
Use the fewest possible connections, saving materials, time, and money.
Eliminate Redundant Connections
No unnecessary loops or duplicate paths are included.
Connect Every Vertex
Every location or device remains reachable.
Simplify Network Design
Spanning trees make computer, road, electrical, and communication networks easier to build and manage.
Serve as the Foundation for Algorithms
Many graph algorithms, such as Minimum Spanning Tree (MST) algorithms (Kruskal's and Prim's), are based on the concept of spanning trees and are widely used in engineering, transportation, and telecommunications.
Applying Breadth-First Search (BFS) and Depth-First Search (DFS) to Find Spanning Trees
A spanning tree is a connected subgraph that includes all vertices of a graph without forming any cycles. Two common algorithms for constructing spanning trees are:
Breadth-First Search (BFS)
Depth-First Search (DFS)
Breadth-First Search (BFS) explores a graph level by level, visiting all neighboring vertices before moving to the next level. It uses a queue (First In, First Out - FIFO) to keep track of vertices to visit.
Choose a starting vertex.
Visit the starting vertex and add it to the queue.
Remove the first vertex from the queue.
Visit all of its unvisited neighbors and add them to the queue.
Repeat until all vertices have been visited.
The edges used to first reach each vertex form the BFS spanning tree.
Visit order:
A → B → C → D → E → F → G
Since every vertex is reached directly from its first discovered parent, these edges form the spanning tree.
Depth-First Search (DFS) explores as far as possible along one branch before backtracking. It uses a stack (Last In, First Out - LIFO) or recursion.
Choose a starting vertex.
Visit the vertex.
Move to one unvisited neighbor.
Continue until no unvisited neighbors remain.
Backtrack to the previous vertex and continue exploring.
The edges used to first reach each vertex form the DFS spanning tree.
(Assume neighbors are visited alphabetically.)
Visit order:
A → B → E → F → C → D → G
The shape depends on the order in which neighbors are chosen.
Comparison of BFS and DFS
Consider the graph:
A
/ \
B---C
\ /
D
Visit order:
A → B → C → D
BFS spanning tree:
A
| \
B C
\
D
Tree edges:
A–B
A–C
B–D
Visit order:
A → B → C → D
DFS spanning tree:
A
|
B
|
C
|
D
Tree edges:
A–B
B–C
C–D
Both BFS and DFS produce a spanning tree when applied to a connected graph.
The spanning tree contains all vertices and exactly n − 1 edges (where n is the number of vertices).
BFS explores neighbors first and is useful for finding the shortest paths in unweighted graphs.
DFS explores one path deeply before backtracking and is useful for graph traversal, cycle detection, and maze solving.
The spanning trees produced by BFS and DFS are often different, depending on the graph structure and the order in which neighboring vertices are visited.
The shortest path problem is the task of finding the minimum distance or lowest cost between vertices in a weighted graph.
Two of the most widely used algorithms are:
Dijkstra's Algorithm – finds the shortest path from one source vertex to all other vertices.
Floyd–Warshall Algorithm – finds the shortest paths between every pair of vertices.
Dijkstra's Algorithm finds the shortest path from a starting vertex (source) to every other vertex in a graph with non-negative edge weights.
It always chooses the nearest unvisited vertex and updates the distances of its neighboring vertices.
Assign the source vertex a distance of 0.
Assign all other vertices a distance of ∞ (infinity).
Select the unvisited vertex with the smallest tentative distance.
Update the distances of its neighboring vertices if a shorter path is found.
Mark the current vertex as visited.
Repeat until all vertices have been visited.
Consider the weighted graph:
From A:
A → B = 2
A → C = 5
From B:
B → D = 3
Distance to D:
2 + 3 = 5
From C:
C → D = 1
Distance through C:
5 + 1 = 6
Since 6 > 5, no update is made.
Consider the graph below.
Find the shortest paths from A.
Update:
A → B = 4
A → C = 2
Update:
A → C → D = 2 + 1 = 3
A → C → E = 2 + 3 = 5
Update:
A → C → D → E = 3 + 2 = 5
No change.
GPS navigation (Google Maps, Waze)
Finding the fastest internet route
Robot path planning
Airline route optimization
Video game character movement
The Floyd–Warshall Algorithm computes the shortest paths between every pair of vertices in a weighted graph.
It works by repeatedly checking whether passing through an intermediate vertex provides a shorter path.
d(i, j) = min (d(i, j), d(i, k) + d(k, j))
where:
d(i, j) is the current shortest distance from vertex iii to vertex jjj,
k is an intermediate vertex.
Initial distance matrix
A → C directly = 10
A → B → C
= 4 + 3
= 7
Since 7 < 10, update A → C to 7
Now the shortest distance between every pair of vertices is known.
Consider the following weighted graph.
Additional edge:
A → D = 10
Check every pair of vertices.
Current distance:
A → D = 10
Going through B:
A → B + B → D
Substitute the values: 2 + 3 = 5
Check every pair.
Current distance:
B → D = 3
Going through C:
B → C + C → D
But B → C = ∞
So ∞ + 1 = ∞
Compare: min (3,∞) = 3
No update is made.
Check every pair.
Since D has no outgoing edges, no shorter paths are found.
Airline route planning
Transportation systems
Social network analysis
Computer network optimization
Dijkstra's Algorithm is best when you need the shortest paths from one source to all other vertices and all edge weights are non-negative.
Floyd–Warshall Algorithm is best when you need the shortest paths between every pair of vertices in the graph.
Both algorithms are fundamental tools in graph theory and are widely used in navigation systems, communication networks, transportation, and logistics.