What is the Depth-First Search Algorithm?

The Depth-First Search (DFS) algorithm is a recursive algorithm that uses the method of backtracking. It involves extensive traversing through all the nodes by going ahead, if possible, else by backtracking.

When you are moving forward and there are no more nodes left along the current path, you go back on the same path to find new nodes to traverse. The next path will only be selected if all the nodes on the current path will be visited. DFS is performed using the stack and it goes as follows:

Pick a source/starting node and push all the adjacent nodes into a stack. Now pick a node from the stack to select the next node to visit and push all its adjacent nodes into a stack.

Repeat the process until the stack is empty. To ensure that all the visited nodes are marked, as this will prevent you from re-visiting the same node. If you do not mark the visited nodes and you may visit the same node more than once and end up in an infinite loop.