Depth-first search (DFS) is a searching algorithm for unweighted graphs. The idea with DFS is that each iteration goes as deep as possible into the graph, then backtracks. When operating on trees, each iteration will go as deep as possible into each branch.
Nodes have three states. They can be undiscovered, discovered, and finished (to denote it’s been completely searched). This ensures that in a cyclic graph, we don’t re-examine the same node. This is an important implication! For trees this isn’t necessary.
When programming a DFS algorithm, we can use an array/structure of Booleans to mark nodes that have been searched.
Analysis
DFS has a time complexity of . For each iteration, we call once per vertex and we then search for every edge. The frontier is stored in a stack.
In a search problem
As a pathfinding algorithm, DFS is a pretty terrible algorithm. However, DFS is useful for yielding valuable information about a graph’s structure.
DFS in its worst case could process the entire search tree. If is finite, then its time complexity is , for the bottom layer of the tree. Its worst case space complexity is , since it stores a path of nodes (i.e., all levels) and at most siblings for each node.
DFS is also not a complete algorithm, since could be infinite (i.e., an infinite search tree). It is also non-optimal.