Depth-First Search

Depth-first search plunges as deep as possible before backtracking, revealing graph structure in O(V + E) time.

Go deep, then back up

Depth-first search (DFS) follows one path as far as it can, then backtracks to the last vertex with an unexplored neighbour and continues. It is naturally recursive, with the call stack holding the current path; an explicit stack gives the same order iteratively. Each vertex is marked visited when first reached so the search never revisits it.

Discovery and finish times

Stamping each vertex with a discovery time when first entered and a finish time when fully explored reveals deep structure. These timestamps classify edges as tree, back, forward, or cross edges, and a back edge signals a cycle. Ordering vertices by decreasing finish time yields a topological sort.

• Time: O(V + E) with an adjacency list
• Space: O(V) for the recursion or explicit stack
• Detects cycles via back edges
• Foundation for topological sort and connectivity

def dfs(graph, u, seen):
    seen.add(u)
    for v in graph[u]:
        if v not in seen:
            dfs(graph, v, seen)

What DFS is good for

DFS drives cycle detection, topological sorting of dependencies, finding strongly connected components, and articulation points and bridges that reveal network vulnerabilities. It is also the traversal behind maze solving and much of backtracking search, where the deep-first order matches the try-then-undo pattern.

BFS or DFS?

Use BFS when you need shortest hop counts or the nearest solution; use DFS when you need to probe full structure, detect cycles, or when solutions tend to lie deep in the search tree. Both visit every vertex and edge once, so both are O(V + E).