Question

Rewrite the explore procedure (Figure 3.3) so that it is non-recursive (that is, explicitly use a stack). The calls to pre visit and post visit should be positioned so that they have the same effect as in the recursive procedure.

Short answer

The recursive procedure is proved.

Step-by-step solution

Step 1: Depth-first search in an undirected graph

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in the downward direction one by one.

Some properties ofdepth-first search are as follows:

1. Using DFT we can verify whether the graph is connected or not it means it detects the cycle present in the graph or not.
2. We can find out the number of connected components by usingdepth-first search.
3. Here we are using the stack as a data structure.

The time complexity of the list is$\mathrm{O}\left(\mathrm{V}+\mathrm{E}\right)$.

The time complexity of the matrix is$\mathrm{O}\left({\mathrm{V}}^2\right)$.

It contains various edges they aretree edge, forward edge, back edge, or cross edge all the edges are explained below:

Tree edge: The graph obtained by traversing while using depth first search is called its tree edge.

Forward edge: the edge$\left\{\mathrm{u},\mathrm{v}\right\}$where is descendant and it is not part of depth first search is called forward edge.

Back edge: the edge $\left\{\mathrm{u},\mathrm{v}\right\}$where is ancestor and it is not part of depth first search is called back edge.

Proving the algorithm

The calls to pre visit and positivist should be positioned so that they have the same effect as in the recursive procedure this algorithm is shown below:

Procedure explore$\left(\mathrm{G},\mathrm{u}\right)$.

$\left(\mathrm{G},\mathrm{u}\right)$

S = ( emptystack)

$\mathrm{push}\left(\mathrm{S},\mathrm{u}\right)$

While S is not empty

v = top(S)

If not visited [ v ]:

visited [ v ] = true

previsit (v)

If there is an edge, then

$\left(\mathrm{v},\mathrm{w}\right)\hat{\mathrm{l}}\mathrm{E}$

withvisited {w] = false:

push(S,w)

else;

Now, the node at the top of the stack.

pop[s]

postvisit [v]

The explore procedure of non-recursive, explicitly use a stack. The calls to previsit and postvisit positioned so that they have the same effect as in the recursive procedure is proved.