Question

Devise an algorithm based on breadth-first search that determines whether a graph has a simple circuit, and if so, finds one.

Short answer

By using the breadth-first search the graph has a simple circuit.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that 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. And a tree with n vertices has n-1 edges.

The breadth-first search method.

In breadth-first search first, choose a root. Add all edges incident to the root. Then each of the vertices at level 1, add all edges incident with ta vertex not included in the tree yet. And repeat until all vertices were added to the tree.

Determine a graph that has a simple circuit.

Let’s select the first vertex\({{\bf{v}}_{\bf{1}}}\). Add all vertices connected to \({{\bf{v}}_{\bf{1}}}\) by an edge to the list L and M and remove the edge from the graph. L will keep track of all vertices checked in the algorithm, while M keeps track of all vertices used in the last step of the algorithm. Then add all vertices connected by an edge to a vertex in M, if one of these vertices in listed in L, then there exists a simple circuit, if no such vertex listed in L is ever found, then there does not exist circuit. If a circuit is found, then use the function P to find the previous element in the circuit. If no vertex was added to the L, then choose a new vertex to add to the list and repeat the procedure for this vertex.

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 = G}}\\{\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 = \{ }}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\end{array}\)

\(\begin{array}{c}{\bf{while}}\,{\bf{L}} \ne {\bf{M}}\\{\bf{if}}\,{\bf{M = }}\phi \,{\bf{then}}\\{\bf{for}}\,{\bf{j = 1}}\,{\bf{ton}}\\{\bf{i}}\,{\bf{f}}{{\bf{v}}_{\bf{j}}} \notin {\bf{L}}\,{\bf{then}}\end{array}\)

\(\begin{array}{c}{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{M = M}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{N = }}\phi \end{array}\)

For every vertex v in M

\({\bf{for}}\,{\bf{j = 1}}\,{\bf{ton}}\)

If \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\)is an edge in G then

\({\bf{if}}\,{{\bf{v}}_{\bf{j}}} \in {\bf{L}}\,{\bf{then}}\)

Remove the edge \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) from T.

Remove the edge \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) from G.

Else Remove the edge from the graph G

\(\begin{array}{c}{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{N = N}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{M = N}}\\{\bf{return}}\,{\bf{T}}\end{array}\)

Therefore, this is the require algorithm.