Python graphs and breadth-first search
An adjacency list maps a vertex to its neighbors. BFS uses a queue to explore discovered vertices in distance order from the start in an unweighted graph.
Python
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return order
graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))
assert bfs({}, "Z") == ["Z"]