Question

Devise an algorithm for constructing the spanning forest of a graph based on depth-first searching.

Short answer

By using the depth-first searching process an algorithm constructs the spanning tree.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G which is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit n vertices has n-1 edges of a tree.

Method for depth-first search.

In depth-first search starts from any randomly chosen root and then creates a path by successively adding vertices to the path that we adjacent to the previous vertex in the path and the vertex that is added must not be in the path.

Algorithm.

Let G be an undirected graph having vertices\({\bf{V = \{ }}{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}......{\bf{,}}{{\bf{v}}_{\bf{n}}}{\bf{\} }}\).

\(\begin{array}{c}{\bf{T = tree}}\,{\bf{with}}\,{\bf{vertex}}\,{{\bf{v}}_{\bf{1}}}\\{\bf{V = \{ }}{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}......{\bf{,}}{{\bf{v}}_{\bf{n}}}{\bf{\} }}\\{\bf{L = \{ }}\,{{\bf{v}}_{\bf{1}}}{\bf{\} }}\\{\bf{m = 1}}\end{array}\)

\(\begin{array}{c}{\bf{first = i}}\\{\bf{while}}\,{\bf{L}} \ne {\bf{V}}\\{\bf{if}}\,{\bf{N = }}\phi \,{\bf{then}}\\{\bf{for}}\,{\bf{i = 1}}\,{\bf{ton}}\end{array}\)

\(\begin{array}{c}{\bf{if}}\,{{\bf{v}}_{\bf{i}}} \notin {\bf{L}}\,{\bf{then}}\\{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_i}{\bf{\} }}\\{\bf{m = i}}\\{\bf{first = i}}\\{\bf{N = }}\phi \\{\bf{for}}\,{\bf{j = 1}}\,{\bf{ton}}\end{array}\)

If \({\bf{(}}{{\bf{v}}_{\bf{m}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) is an edge in G and \({\bf{N = }}\phi \) then

Add the edge \({\bf{(}}{{\bf{v}}_{\bf{m}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) to the graph T

Remove the edge \({\bf{(}}{{\bf{v}}_{\bf{m}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) from the graph G

\(\begin{array}{c}{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{m}}}{\bf{\} }}\\{\bf{N = N}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{m}}}{\bf{\} }}\\{\bf{P}}\,{\bf{(j) = m}}\\{\bf{while}}\,{\bf{N = }}\phi \,\,{\bf{and}}\,\,{\bf{m}} \ne {\bf{first}}\\{\bf{m = P(M)}}\\{\bf{return}}\,\,{\bf{T}}\end{array}\)

Therefore, it can get the construction of spanning forest.