ALGORITHMS FOR CONSTRUCTING SPANNING TREES
An algorithm for finding a spanning tree based on the proof of the theorem : A simple graph G has a spanning tree if and only if G is connected, would not be very efficient, it would involve the time-consuming process of finding cycles. Instead of constructing spanning trees by removing edges, spanning tree can be built up by successively adding edges. Two algorithms based on this principle for finding a spanning tree are Breath-first search (BFS) and Depth-first search (DFS).
BFS algorithm
In this algorithm a rooted tree will be constructed, and underlying undirected graph of this rooted forms the spanning tree. The idea of BFS is to visit all vertices on a given level before going into the next level.
Procedure :
(i) Arbitrarily choose a vertex and designate it as the root. Then add all edges incident to this vertex, such that the addition of edges does not produce any cycle.
(ii) The new vertices added at this stage become the vertices at level 1 in the spanning tree, arbitrarily order them.
(iii) Next, for each vertex at level 1, visited in order, add each edge incident to this vertex to the tree as long as it does not produce any cycle.
(iv) Arbitrarily order the children of each vertex at level 1. This produces the vertices at level 2 in the tree.
(v) Continue the same procedure until all the vertices in the tree have been added.
(vi) The procedure ends, since there are only a finite number of edges in the graph.
(vii) A spanning tree is produced since we have produced a tree without cycle containing every vertex of the graph.
DFS algorithm
An alternative to Breath-first search is Depth-first search which proceeds to successive levels in a tree at the earliest possible opportunity. DFS is also called back tracking.
Procedure :
(i) Arbitrarily choose a vertex from the vertices of the graph and designate it as the root.
(ii) Form a path starting at this vertex by successively adding edges as long as possible where each new edge is incident with the last vertex in the path without producing any cycle.
(iii) If the path goes through all vertices of the graph, the tree consisting of this path is a spanning tree. Otherwise, move back to the next to last vertex in the path, and, if possible, form a new path starting at this vertex passing through vertices that were not already visited.
(iv) If this cannot be done, move back another vertex in the path, that is two vertices back in the path, and repeat.
(v) Repeat this procedure, beginning at the last vertex visited, moving back up the path one vertex at a time, forming new paths that are as long as possible until no more edges can be added.
(vi) This process ends since the graph has a finite number of edges and is connected. A spanning tree is produced.
