1"""
2Breadth-First Search (BFS) - Graph Traversal Algorithm
3
4BFS explores a graph level by level, visiting all neighbors of a node before
5moving to the next level. It uses a queue (FIFO) to track nodes to visit.
6
7Key Properties:
8 - Finds shortest path in unweighted graphs (minimum number of edges)
9 - Explores nodes in order of increasing distance from start
10 - Complete: Will find a solution if one exists (for finite graphs)
11
12Time Complexity: O(V + E) - visits every vertex and edge once
13Space Complexity: O(V) - queue and visited set can hold all vertices
14
15Common Applications:
16 - Shortest path in unweighted graphs
17 - Level-order traversal
18 - Finding connected components
19 - Web crawlers
20 - Social network analysis (degrees of separation)
21 - GPS navigation (minimum hops)
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 collections import deque
30from typing import Dict, Set, List, Any
31
32
33def bfs(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
34 """
35 Perform BFS traversal starting from a given node.
36
37 Args:
38 graph: Adjacency list representation {node: {neighbors}}
39 start: Starting node for traversal
40
41 Returns:
42 List of nodes in BFS order (level by level)
43
44 Raises:
45 ValueError: If start node is not in graph
46 """
47 if start not in graph:
48 raise ValueError(f"Start node '{start}' not in graph")
49
50 visited = {start}
51 queue = deque([start])
52 order = []
53
54 while queue:
55 node = queue.popleft() # O(1) - why we use deque instead of list
56 order.append(node)
57
58 for neighbor in graph[node]:
59 if neighbor not in visited:
60 visited.add(neighbor)
61 queue.append(neighbor)
62
63 return order
64
65
66def bfs_with_levels(graph: Dict[Any, Set[Any]], start: Any) -> Dict[Any, int]:
67 """
68 Perform BFS and return the level (distance) of each reachable node.
69
70 Args:
71 graph: Adjacency list representation
72 start: Starting node
73
74 Returns:
75 Dictionary mapping each reachable node to its level (distance from start)
76 """
77 if start not in graph:
78 raise ValueError(f"Start node '{start}' not in graph")
79
80 levels = {start: 0}
81 queue = deque([start])
82
83 while queue:
84 node = queue.popleft()
85
86 for neighbor in graph[node]:
87 if neighbor not in levels:
88 levels[neighbor] = levels[node] + 1
89 queue.append(neighbor)
90
91 return levels
92
93
94def bfs_shortest_path(graph: Dict[Any, Set[Any]], start: Any, target: Any) -> List[Any] | None:
95 """
96 Find the shortest path between two nodes using BFS.
97
98 In an unweighted graph, BFS guarantees the shortest path
99 (minimum number of edges) because it explores level by level.
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 the shortest 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 queue = deque([(start, [start])]) # (node, path_to_node)
119
120 while queue:
121 node, path = queue.popleft()
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 queue.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("BFS Traversal:", bfs(example_graph, "A"))
156 print("Node Levels:", bfs_with_levels(example_graph, "A"))
157 print("Shortest Path A->F:", bfs_shortest_path(example_graph, "A", "F"))
158