Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far down a branch as possible before backtracking. DFS is widely used in applications like finding connected components, detecting cycles, topological sorting, and solving maze or pathfinding problems.

DFS can be implemented in two main ways: - Recursive DFS: Using function calls to implicitly handle the stack. - Iterative DFS: Using an explicit stack (e.g., a list in Python) to manage nodes.

How DFS Works

DFS starts from a source node, explores each branch completely, and then backtracks to explore other branches. It explores nodes in a depthward motion, moving to a new branch only when the current branch is fully explored.

Key Properties of DFS:

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. DFS visits each node and edge once.
• Space Complexity: O(V) for the recursion stack in the recursive approach or the explicit stack in the iterative approach.
• Traversal Order: DFS does not guarantee any specific order, but it always explores deeper nodes before backtracking.

Use Cases of DFS:

• Cycle Detection: In directed and undirected graphs.
• Topological Sorting: In directed acyclic graphs (DAGs).
• Pathfinding: In scenarios where we need to find a path from a source to a target.
• Connected Components: To identify connected components in an undirected graph.

Graph Representation for DFS

Graphs can be represented in multiple ways, but the two most common representations for DFS are:

1. Adjacency List: A dictionary where each key is a node and its value is a list of adjacent nodes.

2. Adjacency Matrix: A 2D array where the value at position [i][j] indicates the presence (and sometimes weight) of an edge between nodes i and j.

For simplicity, we’ll use the adjacency list representation.

DFS Implementation: Recursive and Iterative

Recursive DFS

The recursive DFS implementation leverages the call stack for tracking visited nodes and backtracking.

from typing import Dict, List

def dfs_recursive(graph: Dict[int, List[int]], node: int, visited: set) -> None:
    """
    Perform DFS recursively on a graph from a starting node.
    - graph: Dictionary representing an adjacency list of the graph
    - node: Current node to visit
    - visited: Set to keep track of visited nodes
    """
    if node in visited:
        return  # Stop if the node is already visited
    visited.add(node)
    print(f"Visited {node}")
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

Example Usage:

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

visited = set()
dfs_recursive(graph, 0, visited)

Explanation

1. Visited Set: Tracks the nodes that have already been visited.
2. Recursive Calls: For each neighbor of the current node, DFS recursively explores unvisited neighbors.
3. Base Case: If the node is already visited, the function stops further recursion.

Iterative DFS

The iterative approach to DFS uses an explicit stack to simulate the recursive process.

def dfs_iterative(graph: Dict[int, List[int]], start: int) -> None:
    """
    Perform DFS iteratively on a graph from a starting node.
    - graph: Dictionary representing an adjacency list of the graph
    - start: The starting node for DFS traversal
    """
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(f"Visited {node}")
            # Add all unvisited neighbors to the stack
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

Explanation:

1. Explicit Stack: Manages which nodes to visit next.
2. Loop: The loop runs until all nodes are visited.
3. Order of Insertion: Reversing the order of neighbors ensures that the traversal order resembles the recursive DFS (left-to-right)

Applications of DFS

1. Cycle Detection: DFS can be used to detect cycles in both directed and undirected graphs. For directed graphs, keeping track of nodes in the current recursion stack can help detect back edges, indicating cycles.
2. Topological Sorting: In Directed Acyclic Graphs (DAGs), DFS is used for topological sorting by processing nodes in reverse postorder.
3. Connected Components: In undirected graphs, DFS can find all nodes connected to a given starting node. Repeating this for all unvisited nodes helps identify connected components.
4. Pathfinding: DFS can find a path from a source to a target in graphs. It’s particularly useful when we need to explore all possible paths.
5. Maze Solving:DFS can be used to solve mazes by exploring paths until either the exit is found or all paths are exhausted.