Back
+20 XP
Concept

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 🌊

# 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>

Checkpoint

What data structure powers Breadth-First Search to explore nodes level-by-level? 🧠

Practice

Implement BFS on `g = {1: [2, 3], 2: [4], 3: [], 4: []}` starting at node `1`. Collect visited nodes into list `order` and print `order`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks