# Title: Breadth-first search
# Heading: Python Program for Breadth-First Search (BFS)
# Level: intermediate
# Tags: bfs, breadth-first search, graph traversal, queue
# Time: O(V + E)
# Space: O(V)
# About: Visits the nodes of a graph from a start node, nearest first, keeping the nodes still to visit in a queue.

from collections import deque


def bfs(graph, start):
    """Every node reachable from start, nearest first."""
    order = []
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)  # so it's queued only once
                queue.append(neighbour)
    return order


# Each node, and the nodes it's joined to by an edge
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
print("BFS from A:", bfs(graph, "A"))