Template: 6. BFS — Level-Order / Shortest Path

6. BFS — Level-Order / Shortest Path

# =============================================================================
from collections import deque

def bfs(start, get_neighbors, is_goal=None):
    queue = deque([start])
    visited = {start}
    level = 0
    while queue:
        for _ in range(len(queue)):  # process one level
            node = queue.popleft()
            if is_goal and is_goal(node):
                return level
            for neighbor in get_neighbors(node):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        level += 1
    return -1


# =============================================================================