Skip to content

BFS — Breadth-First Search

Inherits from: the queue. Data structure: graph + queue। Thinking tweak: layer by layer expand করো — কোনো node-এ প্রথমবার পৌঁছানোই shortest path (যখন প্রতিটা edge-এর cost সমান)।

Inheritance-টা, খুলে বলা

BFS তোমার হাতে আগে থেকেই আছে। ../04-stack-and-queue/-এ শিখেছ, একটা queue জিনিসগুলো arrival order-এ process করে। BFS এর বেশি কিছুই না:

BFS = a queue + a visited set + "neighbors join the back of the line"

Start node queue-তে ঢোকে। তারপর চিরকাল: front pop করো, তার unseen neighbors enqueue করো। Queue first-in-first-out বলে, distance d-এর সবকিছু পুরোপুরি process হয় distance d+1-এর কিছু ছোঁয়ার আগেই। Tree-র level-order traversal (../07-trees/) আসলে এমন এক graph-এ BFS ছিল যার ঘটনাক্রমে কোনো cycle ছিল না — এখানে একমাত্র নতুন উপাদান হলো visited set, কারণ graph পেছনে loop করতে পারে।

যে একটা theorem তোমাকে defend করতে পারতেই হবে

Unweighted graph-এ, BFS কোনো node-কে প্রথমবার যখন discover করে, তখনই সে তার একটা shortest path পেয়ে গেছে।

কেন — সরল কথায়: BFS nodes discover করে strictly non-decreasing distance order-এ — আগে distance 0-এর সব, তারপর distance 1-এর সব, তারপর 2, এভাবে। তাই কোনো node-এর যদি BFS-এর পাওয়া পথের চেয়ে ছোট কোনো route থাকত, সেই ছোট route-এর endpoint আগের কোনো wave-এই discover হয়ে যেত। হয়নি। Contradiction। শেষ।

এজন্যই "minimum number of moves/steps/swaps/transformations" problem মানেই BFS problem, ব্যস — যখন প্রতিটা move-এর cost সমান।

Visited-set discipline

সবচেয়ে common BFS bug:

# WRONG: mark when popped
node = q.popleft()
if node in seen:        # node may already sit in the queue 5 times
    continue
seen.add(node)

# RIGHT: mark when pushed
for nxt in adj[node]:
    if nxt not in seen:
        seen.add(nxt)   # claimed the moment it joins the queue
        q.append(nxt)

Mark-on-pop-ও শেষমেশ terminate করে, কিন্তু queue একই node অনেকবার ধরে রাখতে পারে — এই অপচয় O(V+E)-কে আরও অনেক খারাপ কিছুতে নিয়ে যেতে পারে, আর "queue-তে একবারই আছি" ধরে নেওয়া যেকোনো logic-কে নষ্ট করে। অভ্যাসটা পাকা করো: seen.add থাকে q.append-এর ঠিক পাশে।

আরও দুটো discipline point:

  • collections.deque ব্যবহার করো; list.pop(0) pop প্রতি O(n) আর চুপিচুপি BFS-কে quadratic বানিয়ে দেয়।
  • Start node seen-এ যায় loop-এর আগেই। এটা ভুললে কোনো cycle start-কে re-discover করতে পারে।

Levels ধরে distance — দুটো equivalent style

Style 1: node-এর সাথে distance store করো। "এক target-এর distance"-এর জন্য সবচেয়ে clean।

from collections import deque

def bfs_dist(adj, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in adj[node]:
            if nxt not in dist:             # dist doubles as the visited set
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

Style 2: প্রতিটা outer iteration-এ পুরো একটা layer process করো। যখন level number-টাই answer ("কত minutes / rounds / waves") — তখন সবচেয়ে clean।

def bfs_levels(adj, start):
    seen = {start}
    frontier = [start]
    level = 0
    while frontier:
        next_frontier = []
        for node in frontier:               # everything at distance `level`
            for nxt in adj[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    next_frontier.append(nxt)
        frontier = next_frontier
        level += 1
    return level - 1                        # distance of the farthest node

দুটোই O(V + E)। যেটা problem-এর জন্য বেশি ভালো পড়া যায়, সেটাই নাও।

আসল path-টা reconstruct করতে (শুধু তার length না), discovery-র সময় parent[nxt] = node store করো, তারপর goal থেকে parents ধরে পেছনে হাঁটো — CSES Labyrinth-এর মতো maze problem-এ লাগে।

Multi-source BFS: একসাথে কয়েকটা পাথর ফেলো

Question-এর shape: "প্রতিটা cell-এর জন্য, nearest X-এর distance" বা "spread-টা সবকিছুতে পৌঁছাতে কতক্ষণ লাগে?" (rotting oranges, আগুন ছড়ানো, nearest exit)।

Trick-টা প্রায় অপমানজনক রকম সহজ: queue-টা শুরু করো ALL sources দিয়ে, distance 0-তে। ঢেউগুলো প্রতিটা source থেকে একসাথে ছড়ায়, আর যেখানে ঢেউ মেলে, প্রতিটা node রাখে যে ঢেউ তাকে আগে ছুঁয়েছে তার distance — automatically nearest source।

def multi_source_bfs(adj, sources):
    dist = {s: 0 for s in sources}
    q = deque(sources)                  # the only change: many starts
    while q:
        node = q.popleft()
        for nxt in adj[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

Mental model: পুকুরে একটা পাথরের বদলে এক মুঠো ছুড়ে দিলে। একই ঢেউ, একই code, seeding-এর একটা extra লাইন। Classic uses: Rotting Oranges, 01 Matrix।

(Equivalent framing: একটা fake super-source বানাও, যেটা free edges দিয়ে সব real source-এর সাথে জোড়া, তারপর সেখান থেকে plain BFS চালাও।)

Grid as graph

বেশিরভাগ interview BFS grid-এ ঘটে, যেখানে graph টা implicit:

def grid_bfs(grid, start_r, start_c):
    R, C = len(grid), len(grid[0])
    dist = {(start_r, start_c): 0}
    q = deque([(start_r, start_c)])
    while q:
        r, c = q.popleft()
        for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < R and 0 <= nc < C        # inside the grid
                    and grid[nr][nc] != "#"        # not a wall
                    and (nr, nc) not in dist):     # not yet discovered
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return dist

পাকা করার মতো grid habits:

  • Direction list-টা একবারই লেখো: ((-1,0),(1,0),(0,-1),(0,1)); চারটা diagonal যোগ করো শুধু problem বললে।
  • Index করার আগে bounds check — Python-এর negative index out-of-bounds read-কে crash না করিয়ে চুপিচুপি wrap করে দেয়।
  • Grid বড় হলে booleans-এর একটা visited 2D list, tuples-এর set-এর চেয়ে দ্রুত; শেখার জন্য দুটোই ঠিক আছে।
  • কখনো কখনো grid-টাই graph না: Bus Routes-এ nodes হলো routes, stops না। Code করার আগে সবসময় জিজ্ঞেস করো, "আমার states কী?"

কখন BFS, কখন DFS

You need Use Why
Shortest path / fewest moves (unweighted) BFS distance-order discovery is the whole theorem
"How many rounds until everything is reached" BFS (multi-source) rounds = levels
Just reachability / visit everything either both are O(V+E); pick the one you type faster
Connected components either same cost; DFS is often shorter to write
Cycle detection, ordering, structural facts DFS finish times and the recursion tree carry the info
Very deep graph, recursion limit a risk BFS or iterative DFS no call-stack depth problem
Memory worry on a bushy, shallow graph DFS BFS frontier can hold a whole (huge) level

পকেটে রাখার এক-লাইনের summary: distance matter করলে BFS; structure matter করলে DFS; শুধু reachability হলে যেকোনোটা।

BFS-এর trigger words

"Shortest", "minimum number of steps/moves/operations", "fewest transformations", "level", "nearest", "spread/infect/rot minute by minute", "wave", "all cells' distance to the closest X"।

Representative problems

  • Rotting Oranges — grid-এ multi-source BFS; answer হলো level count।
  • Word Ladder — এক অক্ষর দূরের শব্দদের implicit graph-এ BFS।
  • 01 Matrix — প্রতিটা zero থেকে multi-source BFS।
  • CSES Labyrinth — grid BFS plus parent-pointer path reconstruction।
  • Is Graph Bipartite? — layer by layer BFS coloring (even layers এক রঙ, odd layers অন্যটা)।

Proof সহ reference treatment: cp-algorithms BFS। পরের file: dfs.md — অন্য personality-টা। তারপর shortest-path.md, যেখানে BFS তার queue-টা heap দিয়ে বদলে বড় হয়ে Dijkstra হয়ে যায়।