DFS is an algorithm that traverses or searches tree or graph data structures. Before backtracking, the algorithm follows each branch from the root node.

To aid in graph backtracking, additional memory, typically a stack, is required to keep track of the nodes found thus far along a particular branch. In the 19th century, French mathematician Charles Pierre Trémaux studied a variation of depth-first search to navigate mazes.

An algorithm for navigating or searching through tree or graph data structures is called depth-first search. The method starts at the root node and explores each branch before turning around.

Thus, the basic concept is to begin at the root or any other random node, mark that node, and then advance to the following nearby node that is not marked. Repeat until no unmarked adjacent nodes remain. Return to find more unmarked nodes to cross. Print path nodes last.

To solve the issue, adhere to the instructions listed below:

• Make a recursive function that accepts a visited array and the node's index.
• Print the current node and mark it as visited.
• Using the index of the adjacent node as the argument, traverse all nearby and unmarked nodes before calling the recursive method.

The following is the step-by-step procedure to implement the DFS traversal:

• Create a stack with all of the graph's vertices in it first.
• Select whatever vertex you want to use as the first vertex in the traverse, and add it to the stack.
• After that, raise a non-visited vertex close to the vertex at the top of the stack.
• Repeat steps 3 and 4 until the vertex at the top of the stack has visited all vertices.
• Go back and pop a vertex of the stack if there isn't any vertex left.
• Till the stack is empty, repeat steps 2, 3, and 4.

Applications

• The topological sorting can be implemented using the DFS algorithm.
• It can be applied to determine the routes connecting two vertices.
• We can also use it to find graph cycles.
• DFS technique is also applied to puzzles with a single solution.
• If a graph is bipartite or not, it can be determined using DFS.

Algorithm

Step 1: For each node in G, set STATUS to 1 (ready status).
Step 2: Slide the initial node A up the stack and change its STATUS to 2. (waiting for state)
Step 3: Carry out Steps 4 and 5 until STACK is empty.
Step 4: Pop the top node N. After processing it, set its STATUS to 3. (processed state)
Step 5: Push all of N's neighbours who are in the ready condition (whose STATUS = 1) onto the stack and change their STATUS to 2. (waiting for state)
[FINAL LOOP]
Step 6: Exit

Pseudocode

DFS(G,v) ( v is the vertex where the search starts )    
        Stack S:= {}; ( start with an empty stack )    
        for each vertex u, set visited[u] := false;    
        push S, v;    
        while (S is not empty) do    
           u := pop S;    
           if (not visited[u]) then    
              visited[u] := true;    
              for each unvisited neighbour w of uu    
                 push S, w;    
           end if    
        end while    
     END DFS()  

Conclusion

A randomised parallel algorithm in the complexity class RNC can compute a depth-first search ordering (not necessarily the lexicographic one). However, as of 1997, it was unknown whether We could generate a depth-first traversal in the complexity class NC via a deterministic parallel method.