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.
DFS has a time complexity of . For each iteration, we call once per vertex and we then search for every edge.
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.
As a pathfinding algorithm, DFS is a pretty terrible algorithm. However, DFS is useful for yielding valuable information about a graph’s structure.