What depth-first search is
Depth-first search, often shortened to DFS, is an algorithm for exploring a graph or tree. It starts at a chosen point and explores as far as possible along each path before backing up. Instead of spreading out evenly, it plunges deep down one route until it can go no further, then backtracks to try other routes. This go-deep-first strategy is what gives DFS its name.
Going deep before backtracking
The central idea of depth-first search is to follow a single path as far as it leads before considering alternatives. When it reaches a point with no unexplored options, it backtracks to the last point where another path was available and continues from there. This means DFS fully explores one branch before moving to the next, working its way through the structure by diving deep and retreating as needed.
How DFS keeps track
Depth-first search can be carried out using recursion, where the function calls itself to explore each next point, naturally backtracking as calls return. It can also use an explicit stack, a structure that handles the most recently added item first, to remember where to continue. Either way, DFS also tracks which points it has already visited to avoid going in circles.
DFS compared to BFS
Depth-first search and breadth-first search are two fundamental ways to explore graphs, and they differ in order. BFS explores level by level, visiting nearer points first, while DFS dives deep along one path before trying others. Each has strengths: BFS is good for finding shortest paths in simple graphs, while DFS is well suited to tasks like fully exploring structures and certain kinds of analysis.
Where DFS is used
Depth-first search is used in many problems that involve exploring all the possibilities in a connected structure, such as navigating mazes, analyzing networks, and processing tree or graph structures. Its deep-first nature makes it a natural fit when the goal is to explore every branch thoroughly. As a core graph algorithm, DFS is widely applied in computer science.
Why it matters
Depth-first search is a foundational algorithm for exploring graphs and trees thoroughly. Understanding what DFS is - following each path as deep as possible before backtracking - clarifies a core technique and its contrast with breadth-first search. For anyone learning about algorithms and graphs, depth-first search is an essential concept to understand.
Related on Skillo
See also: What is breadth-first search? Explained, What is a graph data structure? Explained.
Sources
Published date reflects the original event date (2023-07-25). This article is original Skillo editorial written from the sources above; facts were verified in September 2026.
Leave a Reply