Depth-first search (DFS) is a way to explore a tree or graph by following one branch as far as possible before returning to explore another. This lesson introduces the basic idea, explains how a search keeps track of progress, and walks through recursive and iterative implementations.
A graph contains vertices (also called nodes) connected by edges. DFS begins at a chosen starting vertex. In a tree, this is often the root; in a graph, the starting vertex can be selected from among its vertices.
All flashcards
What is depth-first search?
DFS is a traversal or search algorithm that follows one branch as far as possible before backtracking to explore other branches.
What does backtracking mean in DFS?
When a vertex has no undiscovered neighbors left, DFS returns along the current path to an earlier vertex and checks for another unexplored branch.
Why is a stack suited to DFS?
A stack is last-in, first-out, so it naturally tracks the most recent vertex or point in the search to resume after exploring deeper.
What is a discovered vertex?
A discovered vertex is one that the traversal has already reached and marked, so it can avoid processing it repeatedly.
What is a DFS tree?
It is the tree formed by the edges that first reach each newly discovered vertex during DFS; it spans the vertices reached from the starting point.
Quiz questions
What is the defining exploration strategy of depth-first search?Answer: It follows a branch as far as possible before backtracking to explore another branch.
What role does a stack play in DFS?Answer: It keeps track of the current search path or pending vertices so the algorithm can continue or backtrack.
Why should a graph traversal mark vertices as discovered?Answer: To avoid repeatedly visiting vertices, especially when cycles or multiple paths connect them.
When recursive DFS finishes exploring a vertex's descendants, what happens next?Answer: It returns to the earlier call and continues checking that vertex's remaining neighbors.
For the same graph and start vertex, why can recursive DFS and an iterative version that pushes all neighbors at once visit vertices in different orders?Answer: The iterative version may pop the last neighbor pushed first, reversing the neighbor order used by recursive DFS.
Based on the Wikipedia article Depth-first search, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.