Breadth-First Search (BFS) for Shortest Path
Breadth-First Search explores graphs level by level using a queue (`deque`). In unweighted graphs, BFS guarantees finding the shortest path between start and target nodes 🌊.
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
def bfs(start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
bfs("A") # A B C D 🌊
# 10. Breadth-First Search (BFS) for Shortest Path Breadth-First Search explores graphs level by level using a queue (`deque`). In unweighted graphs, BFS guarantees finding the shortest path between start and target nodes 🌊. ```python from collections import deque graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []} def bfs(start): visited = set([start]) queue = deque([start]) while queue: node = queue.popleft() print(node, end=" ") for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) bfs("A") # A B C D 🌊 ``` BFS guarantees that the first time you discover a target node, you took the minimum possible number of hops! 🌊 --- ### Question What data structure powers Breadth-First Search to explore nodes level-by-level? 🧠- [ ] a. A Queue (`collections.deque`) following First-In First-Out (FIFO) 🌊 - [ ] b. A Stack following LIFO - [ ] c. A Binary Max-Heap - [ ] d. A Linked Hash Map --- ### Challenge Implement BFS on `g = {1: [2, 3], 2: [4], 3: [], 4: []}` starting at node `1`. Collect visited nodes into list `order` and print `order`. 🎯 <details> <summary>Solution</summary> ```python from collections import deque g = {1: [2, 3], 2: [4], 3: [], 4: []} order = [] visited = set([1]) queue = deque([1]) while queue: node = queue.popleft() order.append(node) for neighbor in g[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) print(order) ``` </details>