DFS explores a graph by going as deep as possible before backtracking. Using recursion (or an explicit stack), it marks nodes visited and explores each unvisited neighbor recursively. DFS is used for topological sorting, cycle detection, finding strongly connected components, and solving maze problems.
void dfs(vector<vector<int>>& adj, int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v])
if (!visited[u]) dfs(adj, u, visited);
}DFS uses the call stack (recursion) or an explicit stack. When visiting node v, it immediately recurses into the first unvisited neighbor, going as deep as possible before backtracking.
Assign each node a discovery time (when first visited) and finish time (when all descendants are processed). These timestamps reveal tree/back/forward/cross edges and are key to topological sort and SCC algorithms.
A back edge (edge to an ancestor currently on the stack) indicates a cycle. In undirected graphs, any edge to an already-visited non-parent node means a cycle exists.
DFS powers: topological sort (reverse finish order), cycle detection, finding connected/strongly-connected components, solving puzzles, generating mazes, and path finding.
DFS uses which data structure (or technique)?
DFS is commonly used for:
What is the time complexity of DFS?