"""
Breadth-First Search — MAT5EJ302(1) Module III
BFS from a source; computes shortest hop-count distances.
"""

from collections import deque


def bfs(graph, source):
    """
    BFS from source. Computes shortest distances (in hop count).

    Args:
        graph: dict mapping vertex -> list of neighbours
        source: starting vertex

    Returns:
        dist:   dict[vertex] -> shortest distance from source (inf if unreachable)
        parent: dict[vertex] -> predecessor on shortest path (None for source)
    """
    dist = {v: float('inf') for v in graph}
    parent = {v: None for v in graph}

    dist[source] = 0
    queue = deque([source])

    while queue:
        v = queue.popleft()
        for u in graph.get(v, []):
            if dist[u] == float('inf'):   # not yet visited
                dist[u] = dist[v] + 1
                parent[u] = v
                queue.append(u)

    return dist, parent


def shortest_path(parent, source, target):
    """Reconstruct shortest path from source to target."""
    if parent.get(target) is None and target != source:
        return None    # unreachable

    path = []
    v = target
    while v is not None:
        path.append(v)
        v = parent.get(v)
    path.reverse()
    return path


def bfs_verbose(graph, source):
    """BFS with step-by-step output showing queue state."""
    dist = {v: float('inf') for v in graph}
    parent = {v: None for v in graph}
    dist[source] = 0
    queue = deque([source])

    print(f"BFS from {source}:")
    print(f"  Initial queue: {list(queue)}")

    step = 1
    while queue:
        v = queue.popleft()
        print(f"\n  Step {step}: Process {v} (dist={dist[v]})")
        for u in graph.get(v, []):
            if dist[u] == float('inf'):
                dist[u] = dist[v] + 1
                parent[u] = v
                queue.append(u)
                print(f"    → Visit {u} (dist={dist[u]}), queue now: {list(queue)}")
            else:
                print(f"    → {u} already visited (dist={dist[u]}), skip")
        step += 1

    return dist, parent


if __name__ == "__main__":
    print("=== BFS Example 1: Simple Path ===")
    graph1 = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'D'],
        'D': ['B', 'C', 'E'],
        'E': ['D']
    }

    dist, parent = bfs(graph1, 'A')
    print(f"  {'Vertex':>8}  {'Distance':>9}  {'Path'}")
    for v in sorted(dist):
        path = shortest_path(parent, 'A', v)
        path_str = ' → '.join(str(x) for x in path) if path else 'unreachable'
        print(f"  {v:>8}  {dist[v]:>9}  {path_str}")

    print()
    print("=== BFS Step-by-Step ===")
    graph2 = {
        1: [2, 3],
        2: [1, 4, 5],
        3: [1, 5],
        4: [2],
        5: [2, 3]
    }
    bfs_verbose(graph2, 1)

    print()
    print("=== BFS on Disconnected Graph ===")
    graph3 = {
        'A': ['B'], 'B': ['A'],
        'C': ['D'], 'D': ['C'],
        'E': []
    }
    dist, _ = bfs(graph3, 'A')
    for v in sorted(dist):
        d = dist[v]
        reachable = "reachable" if d < float('inf') else "UNREACHABLE"
        print(f"  A → {v}: {d if d < float('inf') else '∞'}  ({reachable})")