1"""
2Depth-First Search (DFS) - Graph Traversal Algorithm
3
4DFS explores a graph by going as deep as possible along each branch before
5backtracking. It uses a stack (LIFO) to track nodes to visit.
6
7Key Properties:
8 - Explores as far as possible before backtracking
9 - Memory efficient for deep graphs (only stores current path)
10 - Does NOT guarantee shortest path (unlike BFS)
11
12Time Complexity: O(V + E) - visits every vertex and edge once
13Space Complexity: O(V) - stack and visited set can hold all vertices
14
15Common Applications:
16 - Topological sorting
17 - Cycle detection
18 - Path finding (any path, not necessarily shortest)
19 - Maze solving
20 - Connected components
21 - Strongly connected components (Tarjan's, Kosaraju's)
22
23Graph Representation:
24 Uses adjacency list format where each node maps to its neighbors.
25 Unweighted: {node: {neighbor1, neighbor2, ...}}
26 Works for both directed and undirected graphs.
27"""
28
29from typing import Dict, Set, List, Any
30
31
32def dfs(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
33 """
34 Perform DFS traversal starting from a given node (iterative).
35
36 Args:
37 graph: Adjacency list representation {node: {neighbors}}
38 start: Starting node for traversal
39
40 Returns:
41 List of nodes in DFS order (depth-first)
42
43 Raises:
44 ValueError: If start node is not in graph
45 """
46 if start not in graph:
47 raise ValueError(f"Start node '{start}' not in graph")
48
49 visited = {start}
50 stack = [start] # Stack instead of queue - the key difference from BFS
51 order = []
52
53 while stack:
54 node = stack.pop() # LIFO: pop from end - O(1)
55 order.append(node)
56
57 for neighbor in graph[node]:
58 if neighbor not in visited:
59 visited.add(neighbor)
60 stack.append(neighbor)
61
62 return order
63
64
65def dfs_recursive(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
66 """
67 Perform DFS traversal using recursion (uses call stack implicitly).
68
69 Args:
70 graph: Adjacency list representation
71 start: Starting node
72
73 Returns:
74 List of nodes in DFS order
75 """
76 if start not in graph:
77 raise ValueError(f"Start node '{start}' not in graph")
78
79 order = []
80 visited = set()
81
82 def _dfs(node: Any) -> None:
83 visited.add(node)
84 order.append(node)
85
86 for neighbor in graph[node]:
87 if neighbor not in visited:
88 _dfs(neighbor)
89
90 _dfs(start)
91 return order
92
93
94def dfs_find_path(graph: Dict[Any, Set[Any]], start: Any, target: Any) -> List[Any] | None:
95 """
96 Find a path between two nodes using DFS.
97
98 Note: Unlike BFS, DFS does NOT guarantee the shortest path.
99 It finds ANY valid path, which may be longer than optimal.
100
101 Args:
102 graph: Adjacency list representation
103 start: Starting node
104 target: Target node to reach
105
106 Returns:
107 List of nodes representing a path, or None if no path exists
108 """
109 if start not in graph:
110 raise ValueError(f"Start node '{start}' not in graph")
111 if target not in graph:
112 raise ValueError(f"Target node '{target}' not in graph")
113
114 if start == target:
115 return [start]
116
117 visited = {start}
118 stack = [(start, [start])] # (node, path_to_node)
119
120 while stack:
121 node, path = stack.pop() # LIFO: pop from end
122
123 for neighbor in graph[node]:
124 if neighbor not in visited:
125 new_path = path + [neighbor]
126
127 if neighbor == target:
128 return new_path
129
130 visited.add(neighbor)
131 stack.append((neighbor, new_path))
132
133 return None # No path found
134
135
136# Example usage and demonstration
137if __name__ == "__main__":
138 # Example graph (undirected, represented with bidirectional edges)
139 #
140 # A
141 # / \
142 # B C
143 # / \ \
144 # D E F
145 #
146 example_graph = {
147 "A": {"B", "C"},
148 "B": {"A", "D", "E"},
149 "C": {"A", "F"},
150 "D": {"B"},
151 "E": {"B"},
152 "F": {"C"},
153 }
154
155 print("DFS Traversal (iterative):", dfs(example_graph, "A"))
156 print("DFS Traversal (recursive):", dfs_recursive(example_graph, "A"))
157 print("DFS Path A->F:", dfs_find_path(example_graph, "A", "F"))
158