Understanding Algorithms (Graphs And Traversal), Part 15: Breadth-First Search (BFS).

Breadth First Search (BFS) is a traversal algorithm that explores nodes level by level from a starting point. It uses a queue to visit neighbors first and is ideal for finding the shortest path in unweighted graphs.

Breadth-First Search is a graph traversal algorithm that explores nodes in expanding layers. Instead of going deep along one path, BFS visits all neighboring nodes first, then moves outward to the next level. This level-by-level approach makes BFS fundamentally different from DFS and gives it unique strengths.

BFS starts from a chosen source node. It first visits all nodes directly connected to the source. Once those nodes are processed, it moves on to their neighbors, and so on. This outward expansion continues until all reachable nodes are visited. The traversal order directly reflects the distance from the source node.

The defining data structure behind BFS is the queue. When a node is visited, it is added to the queue. Nodes are processed in the same order they were discovered. This first-in, first-out behavior enforces level-by-level traversal. Without a queue, BFS cannot maintain its exploration order.

Like DFS, BFS requires a visited structure. Graphs may contain cycles, and without marking visited nodes, BFS could revisit the same node repeatedly. Each node is marked as visited when it is first added to the queue, not when it is removed. This prevents duplicate insertions and unnecessary processing.

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. Every vertex is visited once, and every edge is examined once. The space complexity is also O(V), since the queue can hold a large number of nodes at the same time, especially in wide graphs.

BFS behaves particularly well on unweighted graphs when shortest paths are required. Because nodes are explored in increasing order of distance from the source, the first time a node is reached, the path used is guaranteed to be the shortest. This makes BFS the foundation for shortest path algorithms in unweighted graphs.

This property explains why BFS is used in problems such as minimum moves in games, shortest route in a maze, and network broadcasting. When all edges have equal cost, BFS naturally finds the optimal solution without additional logic.

BFS also exposes the concept of levels explicitly. Each level represents nodes at the same distance from the source. This makes BFS useful for problems involving layers, such as finding all nodes within k steps, computing distances, or grouping nodes by proximity.

In trees, BFS is often called level-order traversal. It processes nodes from top to bottom, left to right. This traversal is commonly used in scenarios where hierarchical breadth matters more than depth, such as scheduling, serialization, and layout computation.

Compared to DFS, BFS tends to use more memory because it stores many nodes at once. However, it provides stronger guarantees about distance and order. This trade-off highlights an important design decision: DFS prioritizes depth and minimal memory, while BFS prioritizes structure and optimal reachability.

BFS is also used as a building block in more advanced algorithms. Bipartite graph checking, connected component labeling, and certain flow algorithms rely on BFS as a core subroutine. These applications extend BFS by adding small amounts of state tracking on top of the traversal.

Breadth-First Search represents a way of thinking about problems spatially rather than sequentially. By expanding evenly in all directions, it mirrors how distance, reachability, and influence spread in real systems. This perspective becomes increasingly important as algorithms move from linear data to networks and large-scale systems.

class BreadthFirstSearch:
    def __init__(self):
        """
        This constructor initializes the Breadth-First Search setup.

        What this represents:
        - A graph traversal technique.
        - Exploration level by level.

        Why this matters:
        - Finds shortest paths in unweighted graphs.
        - Ensures systematic coverage.
        """
        pass

    # --------------------------------------------------
    # BUILD GRAPH (ADJACENCY LIST)
    # --------------------------------------------------
    def build_graph(self, edges):
        """
        Builds a graph using an adjacency list.

        Core idea:
        - Each node stores its neighbors.
        - Connections are explicit.
        """

        graph = {}

        for u, v in edges:
            if u not in graph:
                graph[u] = []
            if v not in graph:
                graph[v] = []

            graph[u].append(v)
            graph[v].append(u)

        return graph

    # --------------------------------------------------
    # BREADTH-FIRST SEARCH
    # --------------------------------------------------
    def bfs(self, graph, start):
        """
        Performs Breadth-First Search on a graph.

        Core idea:
        - Visit nodes level by level.
        - Use a queue to control order.

        Key rule:
        - Track visited nodes to avoid repetition.
        """

        visited = set()
        queue = [start]

        visited.add(start)

        while queue:
            current = queue.pop(0)
            print(current)

            # Visit neighbors
            for neighbor in graph[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

# --------------------------------------------------
# EXAMPLE USAGE
# --------------------------------------------------

edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 5)
]

bfs_algo = BreadthFirstSearch()
graph = bfs_algo.build_graph(edges)

print("BFS Traversal:")
bfs_algo.bfs(graph, 1)