Depth-First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

from typing import Dict, Set, List, Any


def dfs(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
    """
    Perform DFS traversal starting from a given node (iterative).

    Args:
        graph: Adjacency list representation {node: {neighbors}}
        start: Starting node for traversal

    Returns:
        List of nodes in DFS order (depth-first)

    Raises:
        ValueError: If start node is not in graph
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    visited = {start}
    stack = [start]  # Stack instead of queue - the key difference from BFS
    order = []

    while stack:
        node = stack.pop()  # LIFO: pop from end - O(1)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return order


def dfs_recursive(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
    """
    Perform DFS traversal using recursion (uses call stack implicitly).

    Args:
        graph: Adjacency list representation
        start: Starting node

    Returns:
        List of nodes in DFS order
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    order = []
    visited = set()

    def _dfs(node: Any) -> None:
        visited.add(node)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                _dfs(neighbor)

    _dfs(start)
    return order


def dfs_find_path(graph: Dict[Any, Set[Any]], start: Any, target: Any) -> List[Any] | None:
    """
    Find a path between two nodes using DFS.

    Note: Unlike BFS, DFS does NOT guarantee the shortest path.
    It finds ANY valid path, which may be longer than optimal.

    Args:
        graph: Adjacency list representation
        start: Starting node
        target: Target node to reach

    Returns:
        List of nodes representing a path, or None if no path exists
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")
    if target not in graph:
        raise ValueError(f"Target node '{target}' not in graph")

    if start == target:
        return [start]

    visited = {start}
    stack = [(start, [start])]  # (node, path_to_node)

    while stack:
        node, path = stack.pop()  # LIFO: pop from end

        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]

                if neighbor == target:
                    return new_path

                visited.add(neighbor)
                stack.append((neighbor, new_path))

    return None  # No path found


# Example usage and demonstration
if __name__ == "__main__":
    # Example graph (undirected, represented with bidirectional edges)
    #
    #       A
    #      / \
    #     B   C
    #    / \   \
    #   D   E   F
    #
    example_graph = {
        "A": {"B", "C"},
        "B": {"A", "D", "E"},
        "C": {"A", "F"},
        "D": {"B"},
        "E": {"B"},
        "F": {"C"},
    }

    print("DFS Traversal (iterative):", dfs(example_graph, "A"))
    print("DFS Traversal (recursive):", dfs_recursive(example_graph, "A"))
    print("DFS Path A->F:", dfs_find_path(example_graph, "A", "F"))