Depth-First Search (DFS)

Depth-First Search (DFS) is an aggressive graph traversal algorithm. Unlike BFS which explores the graph layer by layer, DFS dives as deep as possible down a single path until it hits a dead end. Only then does it backtrack to explore other paths.

         Core Concept:
        DFS uses a Stack (Last-In, First-Out or LIFO) to keep track of the nodes it
        needs to visit next. This forces the algorithm to explore the most recently discovered nodes
        first, creating that "deep diving" behavior. It is the go-to algorithm for solving mazes,
        topological sorting, and cycle detection.
      

The Maze Explorer Principle

You can think of DFS as navigating a complex maze. Here is how it operates:

Start at your chosen root node and push it onto the stack.
While the stack is not empty, pop the node at the top of the stack. This becomes your current node.
If this current node hasn't been visited yet, mark it as visited.
Look at all its immediate neighbors. Push any unvisited neighbors onto the stack. (Note: We often reverse the neighbors before pushing them so that the first neighbor is at the top of the stack and gets explored first).
When you hit a dead end (a node with no unvisited neighbors), the algorithm naturally backtracks by popping the next available node from the stack.

Algorithm Walkthrough

Below is the Python implementation used in our animation engine. Notice how the stack uses the pop() method to pull from the end of the list, creating the LIFO behavior.

def dfs(start_node):
    stack = [start_node]
    visited = []

    visit(start_node, f"Starting DFS from node {start_node}")

    while len(stack) > 0:
        # Pop from the end of the list (Stack behavior)
        current = stack.pop()

        if current not in visited:
            visited.append(current)
            visit(current, f"Diving into node {current}")

            # Reverse neighbors to explore the first added neighbor first
            for neighbor in reversed(neighbors(current)):
                if neighbor not in visited:
                    stack.append(neighbor)
                    select(neighbor)


# Run the algorithm
dfs("1")

Complexity

Just like BFS, DFS is highly efficient and will visit every connected component of the graph exactly once.

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. Every vertex and edge is explored exactly once in the worst-case scenario.
Space Complexity	$O(V)$	The algorithm requires extra memory for the `stack` and the `visited` list. In the worst-case scenario (e.g., a straight line of nodes), the stack will hold all vertices at once.