Depth First Search

Depth First Search (DFS) is similar to Breadth-First Search (BFS) with the difference in terms of how intermediate elements are held before processing.

While BFS will always process nodes in the order those are found (FIFO), DFS, on the other hand, will process nodes in the reverse order of their discovery (LIFO), i.e., DFS processes the record that is most recently discovered before processing records that were found before.

Consider the same illustration that we used for BFS:

Assuming the start node to be the one with value 1, the nodes that the algorithm will next traverse will be 4 and 5 before traversing 2 (or 2 and 3 before traversing 4).

Like BFS, we use an additional data structure (Stack) to temporarily hold intermediate nodes to block their processing until all the nodes in the current hierarchy are processed. As we know, stack provides LIFO traversal of its elements; it helps us to process the graph elements along the hierarchy instead of their level.

On a high level, the algorithm looks like the following:

1. Initialize discovered stack S with the start node.
2. Initialize visited array V as a boolean array of size equal to the number of vertices.
3. While S is not empty, pop its head element.
4. Return if element is equal to the key we are looking for.
5. Else, mark element as visited in the V array.
6. For all the neighbors adj of element:
   1. if adj is not visited already in the V, and is not discovered in S, push it to S.
   2. return to step 3.

Let’s try this algorithm for the given input for key 3:

1. Discovered: [1]; Visited: [] - We start with a blank visited array, and the discovered stack is initialized with element 1.
2. Discovered: [4, 2]; Visited: [1] - Next, we pop the head of the stack, and as it does not match with the key, we mark it visited. Its neighbors, ‘2’ and ‘4’, are added to the discovered stack.
3. Discovered: [5,2]; Visited: [1,4] - In the next iteration, we pop ‘4’ from the top of the stack, which fails the comparison test and ends up as visited. Its neighbor ‘5’ is added to the top of the stack.
4. Discovered: [2]; Visited: [1,4,5] - Similar to the previous step, ‘5’ is popped from the top of the stack and is marked visited for failing the comparison test.
5. Discovered: [3]; Visited: [1,4,5,2] - In the next step, ‘2’ is popped from the stack and is marked visited as it also fails the comparison test. Its neighbor ‘3’ is added to the stack.

In the next step, when we pop 3 from the top of the discovered stack, it will pass the comparison test and is returned to denote the presence.

public int search(int[][] graph, int start, int key){
    boolean[] visited = new boolean[graph.length];
    Stack<Integer> discovered = new Stack<>();
    discovered.add(start);
    while(!discovered.isEmpty()){
        Integer visitedNode = discovered.pop();
        if(visitedNode == key){
            return visitedNode;
        }
        visited[visitedNode] = true;
        // for each neighbor, check if the two vertices are connected
        // if yes, and the neighbor is not visited already
        // add it to the discovered list
        for(int neighbor = 0; neighbor < graph.length; neighbor++){
            // graph[visitedNode][neighbor] != 0 is neighbor check
            // !visited[neighbor] - is not be visited already
            // !discovered.contains(neighbor) - is not discovered already via some other node
            if(graph[visitedNode][neighbor] != 0 && !visited[neighbor] && !discovered.contains(neighbor)){
                discovered.push(neighbor);
            }
        }
    }
    return -1;
}

Similar to BFS, the overall complexity of this algorithm is dependent on the underlying data structure used to represent the graph:

1. For an adjacency matrix representation, we will have to traverse an entire row of size equal to the number of vertices to discover all the adjacent nodes, so the complexity for V nodes will be \(O(V^2)\).
2. For an adjacency list representation, each node will only have a list of its adjacent elements of size E, and hence the overall complexity becomes \(O(E) + O(V) = O(E+V)\).