concept · INFO-CS-ADS-104Depth-First Search (DFS)
Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.
Explanation
Overview
Depth-First Search (DFS) is a traversal algorithm that visits a vertex and recursively or iteratively explores an unvisited neighbor before backtracking.
Key concepts
name: Core idea; description: The central focus of depth-first search (dfs) is the capability described here: Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.; name: Problem context; description: Depth-First Search (DFS) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using depth-first search (dfs), check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
adjacencyList: O(V + E); adjacencyMatrix: O(V²)
Space complexity
O(V) for visited information and the recursion or explicit stack in the worst case, excluding graph storage.
Applications
Cycle detection; Connected-component identification; Topological sorting; Finding strongly connected components; Maze and state-space exploration; Path existence checking
Advantages
Uses a simple recursive structure.; Supports many advanced graph algorithms.; Can explore deep structures efficiently.; Works on directed and undirected graphs.
Limitations
Does not guarantee shortest paths.; Recursive implementations may exceed the call-stack limit on deep graphs.; Traversal order depends on neighbor ordering.; A disconnected graph requires additional starting vertices to visit every component.
Example or application
A worked example has not yet been added.
Definition
Depth-First Search (DFS) is a traversal algorithm that visits a vertex and recursively or iteratively explores an unvisited neighbor before backtracking.
Core Principle
Explore deeply before backtracking.
Algorithm Steps
Choose a starting vertex.
Mark the starting vertex as visited.
Select an unvisited neighboring vertex.
Continue exploring from that neighbor.
When no unvisited neighbor remains, backtrack.
Continue until all vertices reachable from the starting vertex have been explored.
Recursive Pseudocode
DFS(u): mark u visited; for each neighbor v of u: if v is not visited: DFS(v).
Iterative Pseudocode
Push the starting vertex onto a stack. While the stack is not empty, pop a vertex; if it is unvisited, mark it visited and push its unvisited neighbors.
Possible Traversal
Note
The exact order depends on the order in which neighbors are processed.
Backtracking
Backtracking occurs when DFS reaches a vertex with no remaining unvisited neighbors and returns to an earlier vertex to continue exploration.
Space Complexity
O(V) for visited information and the recursion or explicit stack in the worst case, excluding graph storage.
Applications
Cycle detection
Connected-component identification
Topological sorting
Finding strongly connected components
Maze and state-space exploration
Path existence checking
Articulation-point and bridge algorithms
Advantages
Uses a simple recursive structure.
Supports many advanced graph algorithms.
Can explore deep structures efficiently.
Works on directed and undirected graphs.
Limitations
Does not guarantee shortest paths.
Recursive implementations may exceed the call-stack limit on deep graphs.
Traversal order depends on neighbor ordering.
A disconnected graph requires additional starting vertices to visit every component.
Important Considerations
Always track visited vertices when traversing graphs that may contain cycles.
For undirected cycle detection, distinguish the parent edge from a genuine back edge.
For directed cycle detection, track recursion-stack or node colors.
An iterative implementation can avoid recursion-depth limitations.
Comparison With BFS
BFS
Uses a queue and explores level by level.
DFS
Uses a stack or recursion and explores deeply before backtracking.
Shortest Path
BFS finds minimum-edge paths in unweighted graphs; DFS does not guarantee this.
Common Complexity
Both run in O(V + E) time with adjacency lists.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of depth-first search (dfs) is the capability described here: Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis. |
Problem context | Depth-First Search (DFS) is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using depth-first search (dfs), check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of depth-first search (dfs)? | Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis. |
What should be checked before applying depth-first search (dfs)? | For depth-first search (dfs), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of depth-first search (dfs) be validated? | Trace a representative depth-first search (dfs) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of depth-first search (dfs).
Identify the assumptions, inputs, and conditions relevant to depth-first search (dfs).
Evaluate an application of depth-first search (dfs) for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures