# Depth-First Search (DFS) — Recursive Graph Traversal (C++) ## Overview DFS explores as far as possible along each branch before backtracking. It's used for topological sorting, cycle detection, connected components, and backtracking problems. ## Complexity - Time: **O(V + E)** - Space: **O(V)** (recursion stack) ## Implementation (from repo) `dfs.cpp` contains a concise recursive DFS which marks `vis[s]=1` and recursively visits neighbors. ### Core snippet ```cpp\nvoid dfs(int s, vector<int> adj[], vector<int>& vis) { vis[s]= 1; cout << s << ' '; for (int v : adj[s]) if (!vis[v]) dfs(v, adj, vis); }\n``` ## Practical notes - Beware recursion depth for very deep graphs — consider iterative DFS with an explicit stack if recursion limits are a concern. - For undirected graphs, track parent to avoid treating the parent edge as a back edge in cycle detection. ## Source `https: //github.com/mashrur-rahman-fahim/algorithm/blob/main/dfs.cpp`.