Question

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

Short answer

(a) Order of DFS traversal: $\mathrm{ABCDHGFE}$

Tree edges: $\mathrm{AB},\mathrm{BC},\mathrm{CD},\mathrm{DH},\mathrm{GH},\mathrm{FG},\mathrm{FE}$

Forward edges:$\mathrm{AF},\mathrm{BE}$

Back edge: $\mathrm{FG},\mathrm{EG},\mathrm{ED},\mathrm{DB}$

Pre and Post order are: $\mathrm{A}(1,16),\mathrm{B}(2,15),\mathrm{C}(3,14),\mathrm{D}(4,13),\mathrm{H}(5,12),\mathrm{G}(6,11),\mathrm{F}(7,10),\mathrm{E}(8,9)$

,

(b) Order of DFS traversal: $\mathrm{ABFCDEHG}$

Tree edges: $\mathrm{AB},\mathrm{AH},\mathrm{HG},\mathrm{BF},\mathrm{FC},\mathrm{DE}$

Forward edges: $\mathrm{FE}$

Back edge: $\mathrm{GA},\mathrm{CB}$

Cross edge: $\mathrm{DC},\mathrm{GF},\mathrm{GB}$

Pre and Post order are: localid="1657775037924" $\mathrm{A}(1,16),\mathrm{B}(2,11),\mathrm{C}(4,5),\mathrm{D}(6,9),\mathrm{E}(7,8),\mathrm{F}(3,10),\mathrm{G}(13,14),\mathrm{H}(12,15)$

Step-by-step solution

Step 1: Depth First Search Graph Traversal

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 downward direction one by one.

A graph contains various edges. They are:tree edge, forward edge and back edge. The graph obtained by traversing while using depth first search is called its tree edge. The edge $(\mathrm{u},\mathrm{v})$where u is descendant and it is not part of depth first search is called forward edge. The edge$(\mathrm{u},\mathrm{v})$ where u is ancestor and it is not part of depth first search is called forward edge.

Traverse the graph (a) by depth first search.

(a)

While traversing the graph bydepth-first search, the vertex A is traversed first. From A there are two options B and F and through A traversal is done to B.

From vertex B two options are C and E. Take E as the next vertex then D then using depth first search, go through node H, G and last traverse F. Figure showing graph traversal by depth first search is:

Edge AB in black color is the main edge called tree edge. The edge in blue color for edge AF is called back edge and the edge BE is called as forward edge.

Here the tree edges for the given graph are $\mathrm{AB},\mathrm{BC},\mathrm{CD},\mathrm{DH},\mathrm{GH},\mathrm{FG},\mathrm{FE}$. The forward edges are $\mathrm{AF},\mathrm{BE}$. And the back edge of the graph is $\mathrm{FG},\mathrm{EG},\mathrm{ED},\mathrm{DB}$.The tree edges of the given graph are localid="1657775173067" $\mathrm{AB},\mathrm{AH},\mathrm{HG},\mathrm{BF},\mathrm{FC},\mathrm{DE}.$The forward edge is $\mathrm{FE}$. The back edges are $\mathrm{GA},\mathrm{CB}$and the cross edge of the graph is $\mathrm{DC},\mathrm{GF},\mathrm{GB}$. Hence, after applying depth-first search where the order of traversal is $\mathrm{ABCDHGFE}$ .

The pre and post number of each vertex are given as, $A\left(1,16\right)$ where 1 is pre vertex and 16 is post vertex. First the pre vertex is obtained and then post vertex of the graph is obtained. The final sequence of the pre and post order are $\mathrm{A}(1,16),\mathrm{B}(2,15),\mathrm{C}(3,14),\mathrm{D}(4,13),\mathrm{H}(5,12),\mathrm{G}(6,11),\mathrm{F}(7,10),\mathrm{E}(8,9).$

Hence, pre and post numbers of each vertex are localid="1657775094839" $\mathrm{A}(1,16),\mathrm{B}(2,15),\mathrm{C}(3,14),\mathrm{D}(4,13),\mathrm{H}(5,12),\mathrm{G}(6,11),\mathrm{F}(7,10),\mathrm{E}(8,9)$and the order of DFS traversal is $\mathrm{ABCDHGFE}$ .

Traverse the graph (b) by depth first search.

(b)

Figure showing graph traverse by depth first search is

In this graph, according to depth first search start from the node A, there are two vertices that are linked with A they are B or H but as mentioned in the question that give preference of vertices by their alphabetic order. Hence, after this visit B. From B there is a direct connection with F. So, the next node in this path is F then again F is connected with two nodes that are C and D . Here by alphabetical order traversal, first C is traversed then from C there is no other edge for traversing then go to the back edge which is back track F to D . After D , traverse the other nodes in a same way that are E,G,F .

Blue color in the graph shows cross edge. Black color shows tree edge of the traversal and the red edge shows back edge and the edge in the green shows forward edge.

Pre and post number of the vertex A given is $A\left(1,16\right)$ where 1 is pre vertex and 16 is the post vertex. Similarly, the pre and post number of each vertex of the graph is obtained.

Hence, pre and post numbers of each vertex are $\mathrm{A}(1,16),\mathrm{B}(2,11),\mathrm{C}(4,5),\mathrm{D}(6,9),\mathrm{E}(7,8),\mathrm{F}(3,10),\mathrm{G}(13,14),\mathrm{H}(12,15)$and the order of DFS traversal is $\mathrm{ABFCDEHG}$.