Depth-First Search Algorithm

DFS is an algorithm for navigating or searching through a graph or tree. The algorithm starts from a node, descends to the deepest possible node, and then returns. DFS is based on the principle of depth-first.

The working logic of the DFS algorithm consists of the following steps:

• Select the start node.
• Visit the start node.
• Explore the neighbors of the start node.
• If there are undiscovered neighbor nodes, switch to that node and repeat the steps (recursively or using a chunk data structure).
• When there are no undiscovered neighbor nodes, go back and return to the previous node.
• Repeat the steps until all nodes have been visited.

The DFS algorithm is often used to perform a depth-based tree or graph search. For example, DFS can be used to find a specific node in a tree or to check if a path exists.

There are different variations of DFS, these are:

• Pre-order DFS: Processes nodes before visiting them. This variation can be used to process or build a tree or graph structure.
• In-order DFS: Visits nodes after visiting the left subtrees. This variation can be used to perform ordering operations in the tree.
• Post-order DFS: Traverses subtrees after visiting nodes. This variation can be used to process nodes in the tree or to clean up the structure.

Warning: The DFS algorithm is a powerful algorithm for discovering or searching for nodes in a graph or tree structure. However, it should be used with caution as it can lead to infinite loops in graphs or trees with looped structures.

Example with Java

As an example, consider a graph structure like the one below:

   A
  / \
 B   C
 |   |
 D   E

Let’s create the Graph class to represent this graph structure:

import java.util.ArrayList;
import java.util.List;

class Graph {
    private int V; // Node count
    private List<List<Integer>> adjList; // List holding node connections

    public Graph(int v) {
        V = v;
        adjList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

    public void DFS(int startNode) {
        boolean[] visited = new boolean[V]; 
        DFSUtil(startNode, visited);
    }

    private void DFSUtil(int currentNode, boolean[] visited) {
        visited[currentNode] = true; 
        System.out.print(currentNode + " ");

        for (int neighbor : adjList.get(currentNode)) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }
}

In this example, the Graph class is used to implement the DFS algorithm. With the addEdge method, we specify the connections between the nodes of the graph. With the DFS method we initialize the DFS algorithm and run DFS from a given start node. The DFSUtil method is an auxiliary method that implements DFS.

Now, let’s run the DFS algorithm using the example:

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("DFS traversal (starting from node 0):");
        graph.DFS(0);
    }
}

In this example, we create the Graph class and specify the connections between nodes. Then, we initialize the DFS algorithm with the DFS method and set the start node to 0. Finally, we print the DFS traversal results to the screen.

DFS traversal (starting from node 0):
0 1 3 2 4

In this output, we can see that the DFS algorithm traverses the graph with depth-first priority starting from the start node.