🔁Data Structures Unit 11 Review

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level, visiting all neighbors of a vertex before moving deeper. It relies on a queue to process vertices in first-in, first-out (FIFO) order, which naturally produces this layer-by-layer behavior.

BFS is especially useful for finding the shortest path in unweighted graphs, identifying connected components, and checking whether a graph is bipartite. It runs in $O(V + E)$ time and $O(V)$ space, making it efficient for most graph problems you'll encounter.

Characteristics of BFS

Level-by-level exploration: BFS visits every vertex at distance $k$ from the start before visiting any vertex at distance $k+1$ . This is what makes it "breadth-first" rather than "depth-first."
Shortest path guarantee: In an unweighted graph, the first time BFS reaches a vertex is always via the shortest path (fewest edges). This property does not hold for weighted graphs.
Queue-driven order: A queue enforces FIFO processing. The vertex that was discovered earliest gets explored next, which is exactly what produces the level-order behavior.
Visited tracking: BFS marks vertices as visited when they are enqueued, not when they are dequeued. This prevents the same vertex from being added to the queue multiple times.

Queue-Based BFS Implementation

Here's how BFS works step by step:

Pick a starting vertex. Enqueue it and mark it as visited.
While the queue is not empty:
- Dequeue the front vertex (call it current).
- Process current (print it, record its distance, etc.).
- For each neighbor of current that hasn't been visited, enqueue that neighbor and mark it as visited.
When the queue empties, every reachable vertex has been explored.

A common mistake is marking a vertex as visited only when you dequeue it. If you do that, the same vertex can get enqueued multiple times by different neighbors, wasting time and potentially producing incorrect results. Always mark visited on enqueue.

Pseudocode:

</>Code
function BFS(graph, startVertex):
    queue = new Queue()
    visited = new Set()

    queue.enqueue(startVertex)
    visited.add(startVertex)

    while queue is not empty:
        currentVertex = queue.dequeue()
        process(currentVertex)

        for each neighbor of currentVertex:
            if neighbor is not in visited:
                queue.enqueue(neighbor)
                visited.add(neighbor)

Quick trace example: Consider a graph where vertex A connects to B and C, B connects to D, and C connects to D.

Start: enqueue A → queue: [A], visited: {A}
Dequeue A, enqueue B and C → queue: [B, C], visited: {A, B, C}
Dequeue B, enqueue D (C is already visited) → queue: [C, D], visited: {A, B, C, D}
Dequeue C, D is already visited → queue: [D]
Dequeue D, no unvisited neighbors → queue: []
Done. Traversal order: A, B, C, D

Characteristics of BFS algorithm, Queue Data Structure - Basics Behind

Complexity Analysis

Time complexity: $O(V + E)$

Every vertex is enqueued and dequeued exactly once ( $O(V)$ work). For each vertex, BFS iterates over its adjacency list to check neighbors. Across all vertices, this totals $O(E)$ for a directed graph or $O(2E)$ for an undirected graph (each edge appears in two adjacency lists), which simplifies to $O(E)$ . Combined: $O(V + E)$ .

For a connected graph, $E \geq V - 1$ , so the time complexity simplifies to $O(E)$ .

Space complexity: $O(V)$

The visited set stores up to $V$ entries.
The queue can hold up to $O(V)$ vertices in the worst case. For example, in a star graph (one center vertex connected to all others), all $V - 1$ neighbors enter the queue at once.

Applications of BFS

Finding the shortest path in an unweighted graph

Because BFS discovers vertices level by level, the first time it reaches any vertex is via the minimum number of edges. To actually recover shortest distances:

Initialize a distance array with all values set to $\infty$ (or -1). Set $\text{distance}[\text{start}] = 0$ .
When you enqueue a neighbor, set $\text{distance}[\text{neighbor}] = \text{distance}[\text{current}] + 1$ .
After BFS completes, the distance array holds the shortest path length from the start to every reachable vertex.

To reconstruct the actual path, also store a parent/predecessor for each vertex and trace back from the destination to the start.

Identifying connected components in an undirected graph

Loop through all vertices. When you find one that hasn't been visited, start a BFS from it.
Every vertex reached during that BFS belongs to the same connected component.
Repeat until all vertices have been visited. The number of times you started a new BFS equals the number of connected components.

Checking if a graph is bipartite

A graph is bipartite if you can color every vertex with one of two colors such that no two adjacent vertices share the same color. BFS handles this naturally:

Assign the start vertex color 0. Enqueue it.
For each neighbor of the current vertex, if unvisited, assign it the opposite color and enqueue it. If it's already visited and has the same color as the current vertex, the graph is not bipartite.
If BFS finishes without finding a conflict, the graph is bipartite.

This works because BFS alternates between levels, and in a bipartite graph, adjacent vertices always belong to different levels (different color groups).

🔁Data Structures Unit 11 Review