Depth First Search (DFS): A Comprehensive Guide

4 min readJul 7, 2024

Depth First Search (DFS) is a fundamental algorithm used for traversing or searching tree or graph data structures. Starting from an initial node, DFS explores as far as possible along each branch before backtracking, utilizing a stack data structure to manage the traversal process.

Working Principle:

Starting Point: Select a starting node (e.g., node A). This node will be the root of our search.

2. Traversal Method:

From the starting node, move to one of its neighbors. This is done one neighbor at a time.
Use a stack to keep track of the nodes. Each visited node is pushed onto the stack, and once all its neighbors have been visited, it is popped from the stack.

3. Recursive Exploration:

Each node is explored recursively, visiting all reachable neighbors from that node.
Ensure that each node is visited only once to avoid cycles and redundant work.

4. Completion:

The process continues until all nodes have been visited, ensuring the traversal covers the entire graph.

Example Execution:

Starting at Node A:

Neighbors of A: Nodes B, D, and E are directly reachable.
Move to node B. Push A onto the stack (push(A)). While at B, push B onto the stack (push(B)).

From Node B:

Neighbors of B: Node C is discovered. Push C onto the stack (push(C)).
Neighbors of C: Nodes E and F are reachable from C. Move to node F (push(F)).

From Node F:

Neighbors of F: Node E is discovered. Move to node E (push(E)).

From Node E:

Neighbors of E: Nodes C and A were previously visited, so move to node D (push(D)).

From Node D:

No Unvisited Neighbors: Since all reachable nodes from D have been visited, backtrack to the previous nodes using the stack until returning to the starting node A.

Key Considerations:

Each node must be visited exactly once.
Upon completing the traversal, the search should return to the starting node, ensuring all nodes are visited.

Below is an example of a Depth First Search (DFS) algorithm implemented in Python. This code demonstrates how to traverse a graph using DFS. The graph is represented as an adjacency list, a dictionary where each key is a node and the corresponding value is a list of its neighbors.

# Define the graph as an adjacency list
graph = {
    'A': ['B', 'D', 'E'],
    'B': ['C'],
    'C': ['E', 'F'],
    'D': [],
    'E': ['D'],
    'F': []
}

# Define the DFS function
def dfs(graph, start):
    # Create an empty stack and push the start node
    stack = [start]
    # Create a set to keep track of visited nodes
    visited = set()

    # Loop until there are nodes to process
    while stack:
        # Pop a node from the stack
        node = stack.pop()
        # If the node hasn't been visited yet
        if node not in visited:
            # Mark it as visited
            visited.add(node)
            print(node, end=' ')  # Print the node (or process it in any other way)
            # Push all its neighbors onto the stack
            for neighbor in reversed(graph[node]):  # Reverse for consistent order
                if neighbor not in visited:
                    stack.append(neighbor)

# Call the DFS function starting from node 'A'
dfs(graph, 'A')

stack: A list that serves as the stack to manage the nodes to visit. The search starts by pushing the starting node onto the stack.
visited: A set to keep track of visited nodes to ensure each node is processed only once.

Loop:

While there are nodes in the stack, pop a node from the stack.
If the node hasn’t been visited, mark it as visited and print it (or process it as needed).
Push all unvisited neighbors of the current node onto the stack. Using reversed(graph[node]) ensures the order of traversal matches the typical recursive DFS order.

Running this code will produce an output similar to this (order may vary depending on graph structure):

A B C F E D

Practical Applications:

DFS is widely used in various applications, including: