Depth First Search

Depth-First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. Think of it as navigating a maze by following one path to its end before trying another. It uses a stack (often via recursion) to keep track of its path, making it highly effective for cycle detection, pathfinding, and solving puzzles.

stack = new Stack()

stack.push(src)

mark src as visited

while stack is not empty:

    u = stack.pop()

    for each neighbor v of u:

        if v is not visited:

            stack.push(v)

            mark v as visited