Breadth-First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

from collections import deque
from typing import Dict, Set, List, Any


def bfs(graph: Dict[Any, Set[Any]], start: Any) -> List[Any]:
    """
    Perform BFS traversal starting from a given node.

    Args:
        graph: Adjacency list representation {node: {neighbors}}
        start: Starting node for traversal

    Returns:
        List of nodes in BFS order (level by level)

    Raises:
        ValueError: If start node is not in graph
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()  # O(1) - why we use deque instead of list
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


def bfs_with_levels(graph: Dict[Any, Set[Any]], start: Any) -> Dict[Any, int]:
    """
    Perform BFS and return the level (distance) of each reachable node.

    Args:
        graph: Adjacency list representation
        start: Starting node

    Returns:
        Dictionary mapping each reachable node to its level (distance from start)
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    levels = {start: 0}
    queue = deque([start])

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in levels:
                levels[neighbor] = levels[node] + 1
                queue.append(neighbor)

    return levels


def bfs_shortest_path(graph: Dict[Any, Set[Any]], start: Any, target: Any) -> List[Any] | None:
    """
    Find the shortest path between two nodes using BFS.

    In an unweighted graph, BFS guarantees the shortest path
    (minimum number of edges) because it explores level by level.

    Args:
        graph: Adjacency list representation
        start: Starting node
        target: Target node to reach

    Returns:
        List of nodes representing the shortest path, or None if no path exists
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")
    if target not in graph:
        raise ValueError(f"Target node '{target}' not in graph")

    if start == target:
        return [start]

    visited = {start}
    queue = deque([(start, [start])])  # (node, path_to_node)

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]

                if neighbor == target:
                    return new_path

                visited.add(neighbor)
                queue.append((neighbor, new_path))

    return None  # No path found


# Example usage and demonstration
if __name__ == "__main__":
    # Example graph (undirected, represented with bidirectional edges)
    #
    #       A
    #      / \
    #     B   C
    #    / \   \
    #   D   E   F
    #
    example_graph = {
        "A": {"B", "C"},
        "B": {"A", "D", "E"},
        "C": {"A", "F"},
        "D": {"B"},
        "E": {"B"},
        "F": {"C"},
    }

    print("BFS Traversal:", bfs(example_graph, "A"))
    print("Node Levels:", bfs_with_levels(example_graph, "A"))
    print("Shortest Path A->F:", bfs_shortest_path(example_graph, "A", "F"))