Breath First Search (BFS) in Python

The Graph →

The Python code to find the shortest path in the above ⬆️ graph →

from collections import deque
from typing import List, Tuple, Optional

def bfs(n: int, graph: List[List[int]], source: int) -> Tuple[List[float], List[int]]:
    """
    BFS on a 1-indexed graph (nodes 1..n).
    Returns:
      level[i] = distance from source to i (inf if unreachable)
      parent[i] = predecessor of i in BFS tree (source's parent is itself, -1 if unreachable)
    """
    INF = float('inf')
    level = [INF] * (n + 1)
    parent = [-1] * (n + 1)

    dq = deque([source])
    level[source] = 0
    parent[source] = source

    while dq:
        u = dq.popleft()
        for v in graph[u]:
            if level[v] == INF:
                level[v] = level[u] + 1
                parent[v] = u
                dq.append(v)

    return level, parent


def find_path(source: int, target: int, parent: List[int]) -> Optional[List[int]]:
    """
    Reconstruct path from source to target using parent array.
    Returns None if target is unreachable.
    """
    if parent[target] == -1:  # unreachable
        return None
    path = []
    v = target
    while v != source:
        path.append(v)
        v = parent[v]
        if v == -1:  # safety (shouldn't happen if parent[target] != -1)
            return None
    path.append(source)
    path.reverse()
    return path


if __name__ == "__main__":
    n = 10
    graph = [[] for _ in range(n + 1)]
    graph[1].extend([2, 3, 4])
    graph[2].extend([1, 6])
    graph[3].extend([1, 7, 8])
    graph[4].extend([1, 7])
    graph[5].extend([8, 10])
    graph[6].extend([2, 10])
    graph[7].extend([3, 4, 8, 9])
    graph[8].extend([3, 5, 7])
    graph[9].extend([7, 10])
    graph[10].extend([5, 6, 9])

    source = 1
    level, parent = bfs(n, graph, source)

    # Print levels
    for i in range(1, n + 1):
        print(f"Level of node {i}: {level[i]}")

    print("-"*50)

    # Print shortest paths (only if reachable)
    for i in range(1, n + 1):
        path = find_path(source, i, parent)
        if path is None:
            print(f"No path from {source} to {i}")
        else:
            print(f"Shortest path {source} -> {i}: {' -> '.join(map(str, path))}")

The output →

Level of node 1: 0
Level of node 2: 1
Level of node 3: 1
Level of node 4: 1
Level of node 5: 3
Level of node 6: 2
Level of node 7: 2
Level of node 8: 2
Level of node 9: 3
Level of node 10: 3
--------------------------------------------------
Shortest path 1 -> 1: 1
Shortest path 1 -> 2: 1 -> 2
Shortest path 1 -> 3: 1 -> 3
Shortest path 1 -> 4: 1 -> 4
Shortest path 1 -> 5: 1 -> 3 -> 8 -> 5
Shortest path 1 -> 6: 1 -> 2 -> 6
Shortest path 1 -> 7: 1 -> 3 -> 7
Shortest path 1 -> 8: 1 -> 3 -> 8
Shortest path 1 -> 9: 1 -> 3 -> 7 -> 9
Shortest path 1 -> 10: 1 -> 2 -> 6 -> 10