Nearly Optimal Space Efficient Algorithm for Depth First Search

Jayesh Choudhari, Manoj Gupta, Shivdutt Sharma

We design a space-efficient algorithm for performing depth-first search traversal(DFS) of a graph in $O(m+n{\log }^{\ast }n)$ time using $O(n)$ bits of space. While a normal DFS algorithm…