Depth-First Search (DFS) Algorithm Explained with Examples and Applications

 What is Depth-First Search (DFS)?

Depth-First Search (DFS) is a fundamental algorithm for traversing or searching tree and graph data structures. The algorithm explores as far as possible along each branch before backtracking, making it suitable for pathfinding, topological sorting, and cycle detection tasks.

DFS Algorithm Explanation

DFS can be implemented using either recursion (implicit call stack) or an explicit stack data structure. The core idea is:

• Start at the root (or any arbitrary node for a graph).
• Visit a node and mark it as visited.
• Recursively or iteratively visit all the adjacent unvisited nodes.

Algorithm Steps (for Binary Tree - Recursive)

1. Visit the current node.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.

Algorithm Steps (for General Graph - Iterative with Stack)

1. Push the start node onto the stack and mark it as visited.
2. While the stack is not empty:
   • Pop a node from the stack.
   • Process the node.
   • Push all unvisited adjacent nodes onto the stack and mark them visited.

Python Example Code

1. DFS for Binary Tree (Recursive)

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def dfs_binary_tree(node):
    if not node:
        return
    print(node.val)
    dfs_binary_tree(node.left)
    dfs_binary_tree(node.right)

# Example Usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_binary_tree(root)
    

Output:

1
2
4
5
3

2. DFS for General Graph (Iterative)

def dfs_graph(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            # Push neighbors in reverse order for correct traversal
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

# Example Usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_graph(graph, 'A')
    

Output:

A
B
D
E
F
C

Time and Space Complexity Analysis

Binary Tree

• Time Complexity: $O(n)$ where $n$ is the number of nodes. Each node is visited exactly once.
• Space Complexity: $O(h)$ where $h$ is the height of the tree (due to recursion stack).

General Graph

• Time Complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.
• Space Complexity: $O(V)$ to store the visited nodes and the recursion or stack.

Conclusion

Depth-First Search is a versatile and powerful tool in algorithm design. It is particularly effective when the solution involves deep paths, recursion, or backtracking. A deep understanding of DFS is crucial for solving a wide variety of algorithmic problems efficiently.

References

• Wikipedia - Depth-First Search
• GeeksforGeeks - DFS for a Graph