Language Selection
Choose your preferred programming language
Showing: Python
Depth-First Search (DFS)
Problem Statement
Implement depth-first search (DFS) traversal for both directed and undirected graphs. DFS explores as far as possible along each branch before backtracking.
Input/Output Specifications
- Input: A graph represented as adjacency list and a starting vertex
- Output: List of vertices visited in DFS order
Constraints
- Graph can be directed or undirected
- Graph may contain cycles
- Vertices are numbered from 0 to n-1
- Graph may be disconnected
Examples
Example 1:
Input: graph = [[1,2], [0,2], [0,1]], start = 0
Output: [0, 1, 2]
Explanation: DFS visits 0, then 1, then 2
Example 2:
Input: graph = [[1], [0,2], [1]], start = 0
Output: [0, 1, 2]
Explanation: DFS visits 0, then 1, then 2
Solution Approaches
Approach 1: Recursive DFS
Algorithm Explanation:
- Mark the current vertex as visited
- Add it to the result
- For each unvisited neighbor, recursively call DFS
- Return the result
Implementation:
Python:
def dfs_recursive(graph, start, visited=None, result=None):
"""
DFS using recursion
Time: O(V + E)
Space: O(V) for recursion stack
"""
if visited is None:
visited = set()
if result is None:
result = []
visited.add(start)
result.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, result)
return result
Java:
class Solution {
public List<Integer> dfsRecursive(List<List<Integer>> graph, int start) {
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[graph.size()];
dfsHelper(graph, start, visited, result);
return result;
}
private void dfsHelper(List<List<Integer>> graph, int vertex,
boolean[] visited, List<Integer> result) {
visited[vertex] = true;
result.add(vertex);
for (int neighbor : graph.get(vertex)) {
if (!visited[neighbor]) {
dfsHelper(graph, neighbor, visited, result);
}
}
}
}
Approach 2: Iterative DFS using Stack
Algorithm Explanation:
- Use a stack to simulate recursion
- Push starting vertex onto stack
- While stack is not empty:
- Pop vertex from stack
- If not visited, mark as visited and add to result
- Push all unvisited neighbors onto stack
Implementation:
Python:
def dfs_iterative(graph, start):
"""
DFS using explicit stack
Time: O(V + E)
Space: O(V) for stack
"""
visited = set()
result = []
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
# Add neighbors in reverse order to maintain left-to-right traversal
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return result
Java:
class Solution {
public List<Integer> dfsIterative(List<List<Integer>> graph, int start) {
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[graph.size()];
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int vertex = stack.pop();
if (!visited[vertex]) {
visited[vertex] = true;
result.add(vertex);
// Add neighbors in reverse order
List<Integer> neighbors = graph.get(vertex);
for (int i = neighbors.size() - 1; i >= 0; i--) {
int neighbor = neighbors.get(i);
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
return result;
}
}
Key Insights
- Recursion vs Iteration: Both approaches have O(V + E) time complexity
- Stack Order: In iterative approach, reverse neighbor order to match recursive behavior
- Visited Check: Always check if vertex is visited before processing
- Graph Representation: Adjacency list is most common and efficient
Applications
- Path Finding: Check if path exists between two vertices
- Cycle Detection: Detect cycles in directed graphs
- Topological Sort: Order vertices in DAG
- Connected Components: Find all connected components
- Maze Solving: Navigate through mazes and grids
Common Mistakes
- Forgetting Visited Check: Can lead to infinite loops in cyclic graphs
- Wrong Stack Order: Iterative DFS may give different order than recursive
- Not Handling Disconnected Graphs: May miss some components
- Memory Issues: Deep recursion can cause stack overflow
Follow-up Questions
- BFS vs DFS: When would you use BFS instead of DFS?
- Path Reconstruction: How would you reconstruct the actual path?
- Multiple Components: How would you handle disconnected graphs?
- Weighted Graphs: How does DFS work with weighted edges?
- Directed vs Undirected: What differences exist between the two?
Test Cases
def test_dfs():
# Test case 1: Simple connected graph
graph1 = [[1, 2], [0, 2], [0, 1]]
assert dfs_recursive(graph1, 0) == [0, 1, 2]
# Test case 2: Directed graph
graph2 = [[1], [2], []]
assert dfs_recursive(graph2, 0) == [0, 1, 2]
# Test case 3: Disconnected graph
graph3 = [[1], [0], [3], [2]]
result = dfs_recursive(graph3, 0)
assert 0 in result and 1 in result
assert len(result) == 2
print("All tests passed!")
test_dfs()
Interview Tips
- Start with Recursive: Recursive DFS is easier to implement and understand
- Mention Both Approaches: Show you know both recursive and iterative methods
- Handle Edge Cases: Empty graphs, single vertex, disconnected components
- Discuss Applications: Show understanding of when to use DFS
- Complexity Analysis: Always mention time and space complexity