Exploring Level by Level¶
from collections import deque
graph = {
"A": ["B", "C", "D"],
"B": ["E", "F"],
"C": ["G"],
"D": ["H"],
"E": [],
"F": [],
"G": [],
"H": [],
}
queue = deque(["A"])
visited = []
while queue:
node = queue.popleft()
if node not in visited:
visited.append(node)
queue.extend(graph[node])
print(visited)['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
Breadth-first search explores a graph one layer at a time¶
The graph overview explained who is connected to whom. BFS turns that structure into a strategy: start from one node, visit its immediate neighbors first, then expand outward level by level using a queue.
Core Explanation¶
BFS visits nearby nodes before moving deeper. It is useful when shortest path by number of edges matters or when level-based exploration is important.
Read the figure without code
the node labels show one valid BFS visitation order
the blue start node is visited first
the green nodes are all reached in one edge from
Athe yellow nodes are reached only after the first layer is finished
That is the key BFS promise: finish the current distance layer before moving farther away.
Continuity from the graph overview
The graph notebook introduced adjacency lists. BFS is the first algorithm that systematically consumes those neighbor lists to explore the network.
Worked Example and Practice Lab¶
Iterative BFS with an explicit queue¶
Expected output
Iterative BFS order: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']This version makes the queue visible in code, which is why it is often the clearest first implementation.
Recursive BFS using a queue helper¶
Expected output
Recursive BFS order: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']Reading BFS behavior¶
These short prompts focus on what the queue and visitation order mean.
Explain why BFS uses a queue instead of a stack.
Describe what “level by level” means in your own words.
Give one reason BFS is useful for shortest-hop problems in unweighted graphs.
Explain how BFS differs from a depth-first approach.
Hint
Think about what should happen first: the oldest discovered node or the most recently discovered node.
Guided Practice¶
What data structure is commonly used in breadth-first search?¶
Which nodes belong to the first BFS layer after the start node in the figure?¶
Key Takeaway¶
BFS explores a graph in expanding layers, which makes it a natural fit for shortest-hop reasoning and level-based discovery. DFS will keep the same graph idea but switch the exploration rhythm completely.