Spanning Trees and Breadth-First Search
Spanning Trees and Breadth-first Search
[Spanning Trees] [Hello. This is Rachel Cardell-Oliver from the University of Western Australia]
We have seen that a graph is made up of a set of vertices and a set of edges, where an edge is a pair of vertices.
A spanning tree of a graph is a connected subgraph of G that spans all vertices.
A subgraph of a graph G is any subset of the edges and vertices of G, and a connected subgraph is a one in which there is some path between any two vertices in the graph.
There can be many possible spanning trees for a graph, so we specify that the minimum spanning tree is the spanning tree with minimum total cost. For unweighted graphs (which we consider here) the cost of a tree is the number of edges. So an MST uses the smallest number of edges from the original graph to connect all the vertices.
An MST is a tree because is contains no cycles (we say it is acyclic). It is spanning because it covers every vertex. And it is minimum because it is the smallest cost tree amongst all the possible spanning trees.
For a graph with V vertices, the minimum spanning tree must have V-1 edges.
So that’s nice, but WHY do we care about minimum spanning trees? For many problems that can be described using a graph, we are interested in finding a low cost solution. For example, suppose we need to design a road system to connect several towns. The solution for this problem is a minimum spanning tree of the graph of all possible town connections. The towns are vertices, the roads are edges, and the cost of each road is the cost of building it. The cost of building a road depends on the distance and terrain and climate etc. For our purposes we just need to know that there is some number that we can associate with each pair of towns as the cost of building a road between them.
Later, we will study an algorithms for generating an MST for a weighted graph (Prim). But to start with, let’s consider an algorithm called breadth-first search (BFS) for generating a spanning tree of a graph. This algorithm starts from a given vertex v and constructs a spanning tree for graph G, called the breadth-first tree.
Breadth-First Search Algorithm
This algorithm uses a queue as its main data structure. The basic idea is simple. Starting with queue containing just one node, consider the neighbours of each node. Add any new vertices from the neighbours to the tree until there are no more vertices to be added.
In order to implement BFS we maintain three data structures:
- Q, the queue of vertices to be processed
- An array colour, with values white (0), grey (1) or black (2) for each vertex.
- An array π, which where π(v) contains the immediate parent of v in the spanning tree. That is the edges of the spanning tree are given by (v, π(v))
BFS Algorithm:
Initial step:
put v into the queue Q, colour[v]=white for all vertices v, π(v) is undefined.
Repeated step:
while Q is not empty
dequeue w from the head of Q
for each vertex x adjacent to w
if colour[x] is white then
π(x) = w
colour[x] = grey
enqueue x onto the tail of Q
end if
end for
colour[w] = black
end while
At the end of the BFS search, every vertex in the graph will have the colour black and the parent array π will contain the details of the BFS spanning tree.
Example:
Initially: Q = {1},
colour is white for all vertices
π is undefined for all vertices
Step 1: Q = {1},
Dequeue 1
The vertices adjacent to 1 is 2, which is white.
Set π(2) = 1, colour(2) = grey and enqueue 2
colour(1) = black
Step 2: Q = {2},
Dequeue 2
The vertices adjacent to 2 is 3,5, which are both white.
Set π(3) = 2, colour(3) = grey and enqueue 3
Set π(5) = 2, colour(5) = grey and enqueue 5
colour(2) = black
Step 3: Q = {3,5},
Dequeue 3
The vertices adjacent to 3 are 2,5,6, which are black, grey and white (respectively)
2 and 5 are not white, so we need only consider 6
Set π(6) = 3, colour(6) = grey and enqueue 6
colour(3) = black
Step 4: Q = {5,6},
Dequeue 5
The vertices adjacent to 5 are 2,3,4,6,7
2,3 are black, 6 is grey, so we need only consider 4 and 7.
Set π(4) = 5, colour(4) = grey and enqueue 4
Set π(7) = 5, colour(7) = grey and enqueue 7
colour(5) = black
Step 5: Q = {6,4,7}
Dequeue 6
The vertices adjacent to 6 are 3,5,7
3,5 are black and 7 is grey so nothing more to do this step.
colour(6) = black
Step 6: Q = {4,7},
Dequeue 4
The vertices adjacent to 4 is only 5
5 is already black so nothing more to do this step
colour(4) = black
Step 7: Q = {7},
Dequeue 7
The vertices adjacent to 7 are 5 and 6
5 and 6 are not white so nothing more to do this step
colour(7) = black
Step 8: Q = {},
The queue is now empty so BFS is finished, with colour(v)=black for all vertices.
The result array π gives the edges in the spanning tree:
(2,1),(3,2),(4,5) ,(5,2),(6,3),(7,5)
The code for the BFS algorithm is provided in BFS.java in your Java code bundle.
[ This talk is by Rachel Cardell-Oliver based on the UWA CITS2200 lecture notes ]