Question

Perform a depth-first search on the following graph; whenever there’s a choice of vertices, pick the one that is alphabetically first. Classify each edge as a tree edge or back edge, and give the pre and post number of each vertex.

Short answer

In the given problem, applieddepth-first search where the order of traverse is$ABCFEIDGH$ .

In order first we get the pre vertices of all and then get post vertex of the graph. Which are mentioned in the above diagram. $\mathrm{A}(1,16),\mathrm{B}(2,11),\mathrm{C}(3,10),\mathrm{F}(4,9),\mathrm{E}(5,6),\mathrm{I}(7,8),\mathrm{D}(13,18),\mathrm{G}(14,17),\mathrm{H}(15,16)$

Step-by-step solution

Properties of DFS

Depth First Search (DFS) is an application of graph traversal. It traverses downward 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 that 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 using depth-first search.
3. Here we are using stack as a data structure.

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

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

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

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

Forward edge: the edge$(u,v)$where u is descendant and it is not part of depth first search is called forward edge.

Back edge: the edge $(u,v)$where u is ancestor and it is not part of depth first search is called forward edge.

Trace the graph

While traversing the graph by depth-first search firstly we get the vertices A, from A there are two options B and E and through A we must go to B.

From vertices B we have again two options they are C and E take C as our next vertices then F then by word depth first search going through node E, as there from F there are again two options they are E and I as mentioned in question traverse alphabetically so here after E, F comes that’s why go to F. and from F go to E and at last visit at I. also it contains a different graph that is contain nodes D,G,H. start from the source node D going in a alphabetic orderdepth first searchtraverse G and then H. here in the diagram the edge AB in black color is the main edge called tree edge.

The edge in blue color for example edge AF is called back edge, and the edge BE is called as forward edge.

Now, draw the graph traverse by depth-first search.

Hence, after applying depth-first search where the order of traverse is $ABCFEIDGH.$

Write the vertices

The tree edges are in the graph after traversing $\mathrm{AB},\mathrm{BC},\mathrm{CF},\mathrm{EF},\mathrm{FI},\mathrm{DG},\mathrm{GH}$

And the back edges are as follows AE, BE and DH.

The pre and post-number of each vertex are given as,$A(1,12)$ where

1 is pre vertex and 12 is post vertex.

In order first we get the pre vertices of all and then get post vertex of the graph. Which are mentioned in the above diagram.$\mathrm{A}(1,16),\mathrm{B}(2,11),\mathrm{C}(3,10),\mathrm{F}(4,9),\mathrm{E}(5,6),\mathrm{I}(7,8),\mathrm{D}(13,18),\mathrm{G}(14,17),\mathrm{H}(15,16)$