DFS, or Depth-First Search, is an uninformed search algorithm used to explore or traverse a graph or tree data structure. It starts at an initial node, explores as far as possible along each branch before backtracking, and continues this process until all reachable nodes have been visited or a specific condition is met. DFS operates based on the principle of depth-first traversal.

Here’s how DFS works:

1. Start at a specified initial node in the graph or tree.
2. Mark the current node as visited to keep track of visited nodes.
3. Explore an adjacent unvisited node connected to the current node. If there are multiple adjacent nodes, select one arbitrarily.
4. Recursively apply steps 2 and 3 to the selected adjacent node until a dead-end is reached.
5. Backtrack to the previous node and repeat step 3 for any unvisited adjacent nodes from that node.
6. Continue this process until all nodes have been visited or until a specific condition or goal is reached.

DFS can be implemented using either an iterative approach with a stack data structure or a recursive approach. The stack keeps track of nodes to be visited, and the recursive approach relies on the call stack of the programming language.

DFS is commonly used for tasks such as:

• Graph traversal: Exploring all nodes and edges of a graph.
• Finding connected components: Determining groups of nodes that are connected to each other.
• Cycle detection: Identifying cycles or loops in a graph.
• Pathfinding: Searching for a path between two nodes in a graph.

DFS does not guarantee finding the shortest path between two nodes since it explores a single branch as deeply as possible before backtracking. If the graph is infinite or has cycles, DFS may enter an infinite loop if not properly handled.

Overall, DFS is a fundamental and widely used search algorithm, especially for traversing or exploring graphs and trees.

DFS (Depth First Search) algorithm

In this article, we will discuss the DFS algorithm in the data structure. It is a recursive algorithm to search all the vertices of a tree data structure or a graph. The depth-first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find the goal node or the node with no children.

Because of the recursive nature, stack data structure can be used to implement the DFS algorithm. The process of implementing the DFS is similar to the BFS algorithm.

The step by step process to implement the DFS traversal is given as follows –

1. First, create a stack with the total number of vertices in the graph.
2. Now, choose any vertex as the starting point of traversal, and push that vertex into the stack.
3. After that, push a non-visited vertex (adjacent to the vertex on the top of the stack) to the top of the stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the stack’s top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the stack is empty.

Applications of DFS algorithm

The applications of using the DFS algorithm are given as follows –

• DFS algorithm can be used to implement the topological sorting.
• It can be used to find the paths between two vertices.
• It can also be used to detect cycles in the graph.
• DFS algorithm is also used for one solution puzzles.
• DFS is used to determine if a graph is bipartite or not.

Algorithm

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until STACK is empty

Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

Step 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and set their STATUS = 2 (waiting state)

[END OF LOOP]

Step 6: EXIT

Pseudocode

1. DFS(G,v)   ( v is the vertex where the search starts )    
2.         Stack S := {};   ( start with an empty stack )    
3.         for each vertex u, set visited[u] := false;    
4.         push S, v;    
5.         while (S is not empty) do    
6.            u := pop S;    
7.            if (not visited[u]) then    
8.               visited[u] := true;    
9.               for each unvisited neighbour w of uu    
10.                  push S, w;    
11.            end if    
12.         end while    
13.      END DFS()