Description

Depth First Search is an algorithm for searching a graph by going as deep as possible down one path before backing up and trying the next. Where Breadth First Search uses a Queue to search level by level, DFS uses a Stack (or just recursion — the call stack) to follow branches to the end. It's the natural fit for exhausting all paths: cycle detection, topological sort, connected components, and Backtrack problems. Note: unlike BFS, it does NOT find shortest paths.

Runtime

O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. Space is O(depth) — can hit O(V) on a long chain.

Pseudocode

Add the start node to a stack
While there is a value in the stack
    Pop the top node
    If the node is the one we are looking for, return
    If it is not,
        Mark it as visited
        Add its unvisited neighbors to the stack
If the stack is empty and you didnt find it, there is no path to it.

Code

def dfs(start, target, graph):
    explored = {start: True}
    stack = [start]

    while stack:
        key = stack.pop()  # pop from the end = go deeper
        if key == target:
            return True

        for node in graph[key].neighbors:
            if node not in explored:
                explored[node] = True
                stack.append(node)

    return False  # target not reachable

# recursive version — the call stack IS the stack
def dfs_recursive(key, target, graph, explored=None):
    explored = explored or {key: True}
    if key == target:
        return True
    for node in graph[key].neighbors:
        if node not in explored:
            explored[node] = True
            if dfs_recursive(node, target, graph, explored):
                return True
    return False