On a finite graph, a full traversal with correct visited-state handling reaches every node reachable from its start. Unrestricted tree search can fail to reach a goal on an infinite branch.

How does breadth-first search differ?

It explores by increasing depth, rather than finishing a branch first.

Can DFS have a depth limit?

Yes, but the limit can exclude deeper goals and changes what the search establishes.

AI Glossary / Graphs and symbolic AI / Advanced

Depth First Search

Definition

Depth First Search, usually abbreviated DFS, is a graph or tree traversal strategy that explores one branch as far as it can before returning to explore alternatives. It can be implemented recursively or with an explicit stack. In AI, it is a basic search method for exploring states and possible action sequences.

What it means

DFS follows a branch before investigating its siblings. If a branch ends or has no unvisited continuation, the search returns to the nearest point with an unexplored alternative. The order of neighboring nodes determines which branch it follows first.
“Depth first” does not mean “best first.” DFS does not inherently prefer a short, cheap, or promising route. Finding a goal confirms that a route exists under the modeled transitions, but the first route found need not be optimal.
A traversal can continue until all reachable nodes have been explored, while a goal search may stop at the first success. Those are different stopping rules for the same general exploration strategy.

How it works

Starting at a node, mark it visited and examine its neighbors in a defined order. Visit an unvisited neighbor and repeat. When no unvisited neighbor remains, backtrack. A recursive implementation uses the call stack to remember unfinished work; an iterative implementation maintains that information explicitly.
For a finite graph represented by adjacency lists, a standard full DFS traversal takes O(V + E) time, where V counts vertices and E counts edges. Its visited records and traversal stack can use O(V) additional space. Implicit search trees require a different analysis because the generated state space may be enormous or infinite.
Visited-state handling prevents repeated expansion in a graph with cycles. It does not, by itself, stop an infinite chain of distinct states.

Three practical examples

Dependency inspection: A tool explores which components are reachable through a dependency graph. The direction of each link must match the question being asked. Finding a dependency path does not automatically determine a valid installation order.
Puzzle solving: A solver explores one sequence of legal moves, backtracks at dead ends, and tries alternatives. Repeated-state checks can prevent cycling between previously encountered board configurations. DFS may still find a long solution before a short one.
Workflow analysis: A team traverses modeled process states to inspect reachable branches. If the workflow graph contains disconnected parts, starting from one state will not necessarily visit them all. A complete inventory may require additional starting points.

Think of it this way

Imagine exploring a branching corridor system while recording visited junctions. You follow one corridor until you cannot continue to a new junction, then return to the latest junction with an unexplored route. The order in which you choose corridors affects what you discover first, but it does not make that first route the shortest.

Worked example

Consider an invented directed graph with edges A→B, A→C, B→D, D→G, and C→G. Start at A, choose B before C, and stop when G is first visited. Each edge has unit cost.
DFS visits A, then B, then D, then G. The first discovered goal path is A→B→D→G, containing three edges. However, A→C→G contains only two edges. The example therefore disproves any general claim that DFS finds a shortest path, even when all edges have equal cost.
If traversal continues after visiting G, it backtracks through D and B to A, then visits C. C's neighbor G is already visited, so it is not expanded again. The full first-visit order is A, B, D, G, C. There are five distinct visited nodes, although the graph has two incoming routes to G.
Now add edge D→B. A visited-state check prevents the traversal from repeatedly cycling between B and D. Without appropriate cycle handling, a naive recursive exploration could continue indefinitely on that branch.
Changing A's neighbor order to C before B would find the two-edge path first. That is an ordering effect, not a shortest-path guarantee.

Illustrative case study

Fictional Birch Systems builds a dependency browser for internal applications. Its first version recursively follows every link without recording visited components. A cycle between two shared services causes repeated exploration and eventually a failure.
The team adds visited-state handling and makes neighbor ordering reproducible for reviews. It then discovers a separate reporting problem: the interface calls the first discovered connection the “shortest dependency chain,” although DFS provides no such guarantee.
The browser is revised to distinguish reachability exploration from shortest-path analysis. Tests cover cycles, disconnected components, and multiple routes to the same component. This case is illustrative; it does not report measured reliability or performance from an actual organization.

Common misconceptions and mistakes

“DFS finds the shortest route.” The worked example shows that it may not.
“Recursion is required.” An explicit stack can implement DFS.
“A visited set guarantees termination everywhere.” Infinite graphs can contain infinitely many distinct states.
“One starting node covers every graph component.” Only reachable nodes are covered unless additional starts are used.
“Traversal edges include every graph edge.” A DFS tree records discovery links; other edges can exist.

Business use

Use DFS when the task calls for structured exploration or reachability analysis and its ordering is appropriate. State whether the output is a visited-node list, a discovery tree, a path, or a complete graph inspection.
Check cycle handling, maximum depth, memory use, and behavior on disconnected data. Long chains can exceed a language's recursion limits, making an explicit stack useful. If the objective is a shortest or lowest-cost route, choose and evaluate a search method with the required guarantee rather than inferring that property from DFS's first result.

Check your understanding

Why does the first example path have three edges?

Answer: DFS explores B's branch before C's.

What prevents the added B - D cycle from repeating?

Answer: Correct visited-state handling.

What changes if C is visited first?

Answer: The first goal path changes, while DFS still has no general optimality guarantee.

Related terms

Breadth First Search
Search tree
Depth-limited search
backtracking
stack
graph traversal
visited set
iterative deepening

Learn next

Draw a small directed graph with a cycle and two routes to one goal. Trace DFS under two neighbor orders, record its discovery edges, and compare the first paths with the shortest available route.

Directed graph

Sources

NetworkX, dfs_edges documentation, traversal scope and ordering: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.depth_first_search.dfs_edges.html Cornell University, Depth First Search lecture notes: https://www.cs.cornell.edu/courses/cs2110/2019su/lectures/lec20-board.pdf UC Berkeley CS188, Search project, visited-state handling: https://www-inst.eecs.berkeley.edu/~cs188/su22/project1/

Previous: Depth Next: Depth First Search on Edges