DFS Traversal
Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking. It uses recursion (implicit stack) and is used for connectivity, cycle detection, and topological sorting.
Algorithm (Recursive):
1. Mark current node as visited.
2. For each neighbor, if not visited, recursively call DFS.
Java implementation for adjacency list:
public void dfs(int start) {
boolean[] visited = new boolean[V];
dfsUtil(start, visited);
}
private void dfsUtil(int u, boolean[] visited) {
visited[u] = true;
System.out.print(u + " ");
for (int v : adjList[u]) {
if (!visited[v]) {
dfsUtil(v, visited);
}
}
}
Iterative DFS can be implemented with a stack.
Two Minute Drill
- DFS explores depth-first using recursion or stack.
- Used for connectivity, cycle detection, topological sort.
- Time O(V+E), space O(V) (call stack).
- Recursive version is concise; careful with deep recursion.
Need more clarification?
Drop us an email at career@quipoinfotech.com