Depth First Search

Depth First Search (popularly abbreviated as DFS) is a recursive graph searching technique.

The Algorithm
While doing a DFS, we maintain a set of visited nodes. Initially this set is empty.
When DFS is called on any vertex (say ), first that vertex is marked as visited and then for every edge going out of that vertex, , such that is unvisited, we call DFS on .
Finally, we return when we have exhausted all the edges going out from .
Hence, if a graph is represented in the standard adjacency list form (a vector of vectors in C++), the C++ implementation follows:

void dfs(int node)  {
  seen[node] = true;
  for(int next: graph[node])  {
    if(not seen[next])  {
      dfs(next);
    }
  }
}

One may note that recursive calls imitate stack push and pop. Hence, DFS can also be implemented using stacks. In cases where the system stack size (which is used for recursion) is very limited, one might use a user-created stack to perform DFS within the memory limits.

The Complexity and Correctness
The above code provides a good angle to view at the complexity. Under no circumstance, DFS will be called twice on a node. For every node, we have iterations equal to the degree of that node. Hence the time complexity is simply sum of degrees of all the nodes which is .
If DFS is called on a node , and there exists a path then DFS will definitiely visit .
This can be proven as an induction on the path length of by observing that DFS indeed visits all nodes which have a direct edge from the first node and hence establishing the base case i.e. for path length = .

Applications
DFS is probably the most used graph-algorithm in programming contests. Many of the standard applications include - searching, counting connected components and their sizes, providing a useful way to number the vertices of a tree, finding bridges, finding euler path/tour and many others.
We'll discuss about numbering the vertices of a tree.
Assume that you have a rooted tree and called a DFS on the root. Now, consider any arbitrary call the DFS makes, say its on node . Now, you can notice that DFS first visits all the nodes in 's subtree and only then visits any other node. Hence, if we number the nodes in the order they are visited, all the nodes in a particular subtree will come under a contigous range.
This kind of numbering is useful for questions which ask to modify all nodes in a particular node's subtree. Doing this converts the problem to a range modification one which are pretty standard.

 
Related challenge for Depth First Search
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score