Depth-First Search (DFS) — Graph Traversal Guide
In this tutorial, you'll learn about Depth. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before Backtracking. It uses a stack (either explicitly or via Recursion) to track the traversal path.
What You'll Learn
You will learn recursive and iterative DFS, pre-order and post-order traversal, cycle detection in directed graphs, topological sorting, and connected component finding.
Why It Matters
DFS is fundamental for solving problems involving paths, connectivity, and dependency resolution. It's used in Garbage Collection, maze solving, puzzle games, and web crawling.
Real-World Use
Durga Antivirus Pro uses DFS to analyze Process trees for malware detection. When scanning for suspicious processes, it traverses the Process tree depth-first to identify parent-child relationships and detect unauthorized code injection chains.
DFS Flow
graph TD
A[Start: A] --> B[B]
A --> C[C]
B --> D[D]
B --> E[E]
C --> F[F]
C --> G[G]
D --> H[H]
E --> I[I]
style A fill:#4a90d9,stroke:#333,color:#fff
style H fill:#e67e22,stroke:#333,color:#fff
style I fill:#e67e22,stroke:#333,color:#fff
style G fill:#e67e22,stroke:#333,color:#fff
DFS order: A → B → D → H → E → I → C → F → G
Recursive DFS
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I'],
'F': [],
'G': [],
'H': [],
'I': []
}
print("DFS:", end=" ")
dfs_recursive(graph, 'A')
Expected output:
DFS: A B D H E I C F G
function dfsRecursive(graph, node, visited = new Set()) {
visited.add(node);
process.stdout.write(node + " ");
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfsRecursive(graph, neighbor, visited);
}
}
return visited;
}
const graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I'],
'F': [],
'G': [],
'H': [],
'I': []
};
process.stdout.write("DFS: ");
dfsRecursive(graph, 'A');
console.log();
Expected output:
DFS: A B D H E I C F G
Iterative DFS
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=" ")
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return visited
print("DFS iterative:", end=" ")
dfs_iterative(graph, 'A')
Expected output:
DFS iterative: A B D H E I C F G
Cycle Detection in Directed Graph
def has_cycle(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False
for node in graph:
if color[node] == WHITE:
if dfs(node):
return True
return False
cyclic = {'A': ['B'], 'B': ['C'], 'C': ['A']}
acyclic = {'A': ['B'], 'B': ['C'], 'C': []}
print("Cyclic:", has_cycle(cyclic))
print("Acyclic:", has_cycle(acyclic))
Expected output:
Cyclic: True
Acyclic: False
Topological Sort
Topological sorting orders nodes so that for every edge u → v, u comes before v. Only possible for Directed Acyclic Graphs (DAGs):
def topological_sort(graph):
visited = set()
stack = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1]
dag = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['F'],
'F': []
}
print("Topological order:", topological_sort(dag))
Expected output:
Topological order: ['B', 'D', 'A', 'C', 'E', 'F']
Finding Connected Components
def connected_components(graph):
visited = set()
components = []
def dfs(node, component):
visited.add(node)
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, component)
for node in graph:
if node not in visited:
component = []
dfs(node, component)
components.append(component)
return components
undirected = {
'A': ['B'], 'B': ['A', 'C'], 'C': ['B'],
'D': ['E'], 'E': ['D'],
'F': []
}
print("Components:", connected_components(undirected))
Expected output:
Components: [['A', 'B', 'C'], ['D', 'E'], ['F']]
Common Pitfalls
1. Not Tracking Visited Nodes
Without a visited set, DFS enters infinite loops on cyclic graphs. Always check if node not in visited before recursing.
2. Stack Overflow in Deep Recursion
Python's Recursion limit (~1000) is easily hit with large graphs. Use iterative DFS with an explicit stack for production code.
3. Reversing Neighbor Order in Iterative DFS
Without reversed neighbors, iterative DFS visits children in different order than recursive DFS. This rarely matters but can affect certain algorithms.
4. Not Handling Disconnected Graphs
DFS starting from a single node only visits reachable nodes. For disconnected graphs, iterate over all nodes.
5. Forgetting Backtracking State
In cycle detection, using only visited/unvisited (not the three-color system) fails. You need GRAY (in current path) to detect back edges.
Practice Questions
1. Find all paths from source to target in a directed graph.
2. Determine if an undirected graph is bipartite using DFS with coloring.
def is_bipartite(graph):
color = {}
def dfs(node, c):
if node in color:
return color[node] == c
color[node] = c
return all(dfs(neighbor, 1 - c) for neighbor in graph[node])
return all(dfs(node, 0) for node in graph if node not in color)
bipartite = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
print(is_bipartite(bipartite))
Expected output: True
3. Clone a graph (deep copy of all nodes and edges) using DFS.
4. Challenge: Implement Kosaraju's algorithm to find strongly connected components in a directed graph using DFS.
5. Real-world task: Durga Antivirus Pro analyzes Process trees for suspicious behavior. Write a DFS-based function that takes a Process tree (parent-child relationships) and detects processes that have been injected by an unauthorized parent (the child runs under a different user context than its parent).
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro