We are using the adjacency list representation of the directed graph from the previous recipe, Creating an adjacency list representation of a directed graph:
The temp1 pointer is set to point to startList, that is, at node a, which we have assumed as the starting vertex of the graph. We then ensure that if temp1 is not NULL, then the node pointed to by the temp1 pointer is pushed to the stack. The value of top, which is initially -1, is incremented to 0 and node a is added to the array of the nodes stack at index location 0, as follows:
Thereafter, the pop function is invoked to remove the node from the stack. The node at the stack[0] index location is returned and the value of top is again decremented to -1.
The node containing vertex a is returned to the temp3 pointer. The temp1 pointer is set to point to the startList pointer. The marked member of the temp3 node, that is, vertex a, is set to N initially. The vertex name stored in the nme member of the node is displayed, that is, vertex a, is displayed on screen. After displaying vertex a, its marked member is set to Y to indicate that the node is visited and should not be traversed again. The temp2 pointer is set to point to where the edg pointer of temp3 is pointing. The edg pointer of temp3 is pointing to vertex b, so temp2 is set to point to vertex b. Again, the procedure is repeated, that is, we check whether temp2 is not NULL, and then node b is pushed to the stack at the stack[0] index location. Because all of the nodes that are connected to vertex a have to be pushed to the stack, the temp2 pointer is set to point to the location that its edg pointer is pointing to. The edg pointer of node b (in the adjacency list) is pointing to node c, so node c is also pushed to the stack at the stack[1] index location, as follows:
In the stack, nodes b and c are present. Now, again, the pop function is invoked, and the node, c, is popped from the stack and the temp3 pointer is set to point to it. The temp1 pointer is initially set to point to startList and, thereafter, by making use of its vrt pointer, the temp1 pointer is set to point to vertex c. Because the marked member of node c is N, its vertex name, c, is displayed on screen and its marked member is set to Y. So, up until now, nodes a and c are displayed on screen.
A temp2 pointer is set to point to where the edg member of node c is pointing. The edg member of node c is pointing to node d, so the d node is pushed to the stack and the next adjacent node of c is accessed. The next adjacent node of node c is node e, which is also pushed to the stack as follows:
Again, the topmost node from the stack, node e, is popped, and the temp3 pointer is set to point to it. Again, the temp1 pointer is set to point to vertex e, and node e is displayed on screen, that is, it is traversed. Then, its marked member is set to Y, and the node that is attached to the edg member of e is pushed to the stack, that is, node a is pushed to the stack, followed by node b, as shown here:
Node b is popped and the temp3 pointer is set to point to it. The temp1 pointer is set to point to node b. Because the marked member of node b is N, stating that it is not yet traversed, vertex b is displayed on screen and its marked member is set to Y. Since there is no adjacent member of vertex b, the next node, a, in the stack is popped. Because vertex a has already been visited, the next node from the stack is popped: node d. The procedure is repeated, and the sequence of vertices displayed is considered as the depth-traversal of the graph.
The program is compiled using GCC, as shown in the following screenshot. Because no error appears during the compilation, this means the depthfirsttrav.c program has successfully compiled into the depthfirsttrav.exe file. On executing the file, the user will be prompted to specify the count of vertices in the graph, followed by entering the vertices' names. Thereafter, the user is asked to enter the edges of the graph and enter 0 0 when completed. After the edges of the graph are entered, the adjacency list representation of the graph will be displayed, followed by the depth-first traversal of the graph, as shown in the following screenshot:
Now, let's move on to the next recipe!