Graph BFS — KLAR

Phase 1f(x)

The Mathematics

Graph definitions, BFS properties, and shortest path theorem

Graph Definition

A graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E \subseteq V \times V$ . We represent it using an adjacency list:

\text{Adj}(v) = \{u \in V : (v, u) \in E\}

For an undirected graph, if $(u,v) \in E$ then $(v,u) \in E$ .

BFS Layer Structure

BFS explores vertices in order of their distance from the source $s$ . Define layers:

L_d = \{v \in V : \text{dist}(s, v) = d\}

$L_0 = \{s\}$ — the source itself

$L_1 = \text{Adj}(s) \setminus L_0$ — direct neighbors

$L_{d+1} = \{u : (v,u) \in E, v \in L_d\} \setminus \bigcup_{i \leq d} L_i$ — new vertices reachable from layer $d$

FIFO Queue Property

BFS uses a First-In-First-Out queue. This ensures that all vertices at distance $d$ are processed before any vertex at distance $d+1$ :

\text{Queue order:}\; L_0, L_1, L_2, \ldots

Shortest Path Theorem

Theorem

For an unweighted graph $G = (V,E)$ and source $s$ , BFS computes $\text{dist}(s,v)$ for all $v \in V$ reachable from $s$ , where $\text{dist}(s,v)$ is the minimum number of edges on any path from $s$ to $v$ .

Complexity: Each vertex is enqueued and dequeued at most once, and each edge is examined at most twice (once from each endpoint):

T(V, E) = O(|V| + |E|)

Phase 2▶

See It Work

BFS traversal from node A — watch the queue and distance layers

Queue (FIFO)

front

A

back

Layer 0 (d=0)

Layer 1 (d=1)

Layer 2 (d=2)

Layer 3 (d=3)

L_0 = \{s\},\; \text{dist}(s,s) = 0

Step 1 of 8

Initialize: enqueue source node A. Mark A as visited with distance 0.

Phase 3</>

The Code

Mapping graph theory to Python with collections.deque

Mathematical Formulation

\text{visited} = \{s\}

Initialize visited set with the source node

Q = \text{deque}([s])

FIFO queue ensures layer-by-layer traversal

\text{dist}(s) = 0

Source has distance 0 from itself

v = Q.\text{popleft}()

Dequeue the front node (FIFO order)

\forall u \in \text{Adj}(v)

Iterate over all neighbors in adjacency list

\text{dist}(u) = \text{dist}(v) + 1

Distance grows by 1 each layer — shortest path in unweighted graph

Python Implementation

from collections import deque

def bfs(graph, source):
    visited = {source}              # Track visited nodes
    queue = deque([source])         # FIFO queue
    dist = {source: 0}             # Distance from source
    while queue:                    # Process until empty
        v = queue.popleft()         # Dequeue front
        for u in graph[v]:          # Visit neighbors
            if u not in visited:    # Skip if seen
                visited.add(u)      # Mark visited
                dist[u] = dist[v] + 1  # Set distance
                queue.append(u)     # Enqueue neighbor
    return dist