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. DFS uses a LIFO Stack (or recursion - which uses the call stack) to follow branches to the end.
?

Reach for when:

You need to check a path rather then a top down search.

Runtime

O(n^2)

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

Queue

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

def dfs_recursive(node, target, explored):
    explored = explored or {node: True}
    if node.key == target:
        return True
    for neighbor in node.neighbors:
        if neighbor not in explored:
            explored[neighbor] = True
            if dfs_recursive(neighbor, target, explored):
                return True
    return False