Depth First Search (DFS) for traversing a Graph

Depth First Search (DFS) is an algorithm for traversing a graph or a tree(any acyclic connected graph is a tree).

We start at a starting node, traverse on a single path in the graph, backtrack when the path ends and again traverse non-visited paths while backtracking.

DFS has the following time and space complexity for traversing an entire Graph having V nodes and E edges:-
1. Time complexity – Θ(|V| + |E|)
2. Space complexity – O(|V|)

In DFS, while traversing, we need to store the nodes on the current search path on a Stack. If we implement a recursive solution, then we do not need an explicit stack. We also need to store the set of already visited nodes to avoid visiting the same node again if there is a cycle in the graph.

DFS Algorithm

We can have recursive as well as non-recursive implementation of DFS. In non-recursive implementation we need to maintain an explicit stack. We will see algorithms for both the approcahes.

Algorithm for recursive DFS

//Call the function dfs() by providing the starting node n and the Graph g
dfs(node n, Graph g){
    Mark node n as visited
    For each (adjacent node w of node n) { 
            If (w is not already visited) { 
                call dfs(w, g) 
            }
    }            
}

Algorithm for non-recursive DFS using Stack

//Call the function dfs() by providing the starting node n and the Graph g
dfs(node n, Graph g){
    S.push(n) // S is a Stack
    while (S is not empty){
         n = S.pop()
         if (n is not already visited) {      
            Mark node n as visited
            For each (adjacent node w of node n) { 
                S.push(w) 
            }
         }
    }         
}

In DFS all nodes on the traversal paths are visited at least two times, except the last nodes on all the visited paths. A node is visited once when we first visit that node, and the node is visited for the last time when we are done with visiting all the next adjacent nodes of this node and backtrack to the node up in the traversal path.
This gives us the way to linearly order the vertices of the original graph.

1. Pre-Ordering – If we list the vertices in the order in which they are first visited by DFS traversal then the ordering is called Preorder.
2. Post-Ordering – If we list the vertices in the order in which they are last visited by DFS traversal then the ordering is called PostOrder.
3. Reverse Post-Ordering – The reverse of a post-ordering and is not the same as preordering. Reverse postordering produces a Topological sorting of any directed acyclic graph.

Consider the following graph-

 

We will see the DFS traversal and ordering on the above graph. We will start our traversal with node 1.
Path traversed – contains the path traversed by the DFS algorithm.
Visited – contains the list of visited nodes.
Preorder – contains the Preorder traversal sequence of the graph.
Postorder – contains the Postorder traversal sequence of the graph.

 

 

Java Implementation

We will see the Java implementation of DFS which computes pre-order and post-oder traversals of any given graph.

    public static void dfs(int node, Map<Integer, int[]> graph, Set<Integer> visited, List<Integer> preOrder, List<Integer> postOrder) {
        // This is the first visit of this node, therefore add it to Pre-Order ordering
        preOrder.add(node);

        // Add this node to the visited nodes' list
        visited.add(node);

        // Process the adjacent nodes of this node
        for (Integer adjacent : graph.get(node)) {
            if (!visited.contains(adjacent)) {
                // If the adjacent node is not already visited, then call dfs() on this adjacent node recursively
                dfs(adjacent, graph, visited, preOrder, postOrder);
            }
        }

        // This is the last visit of this node, therefore add it to the Post-Order ordering
        postOrder.add(node);
    }

Lets write a main() method to call the above dfs()  function for the above graph. We will start DFS from node 1 and print the pre-order and post-order traversals.

    public static void main(String[] args) {

        //Create the graph as adjacency list
        Map<Integer, int[]> graph = new HashMap<Integer, int[]>();
        graph.put(1, new int[] { 2, 3 });
        graph.put(2, new int[] { 4, 5 });
        graph.put(3, new int[] { 6 });
        graph.put(4, new int[] {});
        graph.put(5, new int[] { 6 });
        graph.put(6, new int[] {});

        //Set to maintain visited node's
        Set<Integer> visited = new HashSet<Integer>();

        //Node to start the dfs traversal
        int startNode = 1;

        // This list will maintain the Pre-Order ordering
        List<Integer> preOrder = new ArrayList<Integer>();

        // This list will maintain the Post-Order ordering
        List<Integer> postOrder = new ArrayList<Integer>();

        //Call dfs 
        dfs(startNode, graph, visited, preOrder, postOrder);

        //Print the pre-order
        System.out.println("Pre-Order ordering - " + preOrder);
        //print the post-order
        System.out.println("Post-Order ordering - " + postOrder);

    }

Running the program produces the following output:-

Pre-Order ordering - [1, 2, 4, 5, 6, 3]
Post-Order ordering - [4, 6, 5, 2, 3, 1]

Applications of DFS

DFS has a variety of applications in Graph processing. Some of the applications are:-

1. Find number of Connected components
2. Check if two nodes in a graph are reachable
3. Find maximum depth of a tree
4. Find all possible paths from a node to all other nodes
5. Print all the paths having length greater than 5 from a given node in graph