DFS — Depth-First Search¶
Inherits from: the stack. Data structure: graph + stack (প্রায়ই call stack-টাই)। Thinking tweak: একটা path-এ commit করো, যতটা পারো গভীরে যাও, আটকে গেলেই কেবল ফিরে এসো — সুতোর বল নিয়ে গুহা explore করার মতো।
Inheritance-টা, খুলে বলা¶
DFS হলো stack-এর traversal, ঠিক যেভাবে BFS হলো queue-র:
Stack last-in-first-out বলে, সবচেয়ে সম্প্রতি discover হওয়া node-টাই পরে explore হয় — তাই search টা siblings try করার আগে এক path ধরে নিচে ঝাঁপ দেয়। BFS-এ একটা শব্দ বদলাও — popleft → pop — আর তোমার হাতে iterative DFS। ওই একটা শব্দই personality-টা পুরো বদলে দেয়।
Recursion = একটা implicit stack¶
বিখ্যাত তিন-লাইনের DFS:
def dfs(node, adj, visited):
visited.add(node)
for nxt in adj[node]:
if nxt not in visited:
dfs(nxt, adj, visited)
কোনো দৃশ্যমান stack নেই — কারণ Python-এর call stack-টাই stack। প্রতিটা recursive call একটা frame push করে ("আমি node X-এ আছি, তার neighbor list-এর মাঝপথে"); প্রতিটা return একটা pop করে। visual-explanation.md Part 2-এর frame-by-frame trace-এ এই stack-টাকেই A B D F E C পর্যন্ত বাড়তে আর গুটিয়ে যেতে দেখেছ।
Iterative জমজটা, যখন recursion depth একটা risk (Python-এর default limit ~1000 frames, আর 10^5 nodes-এর একটা path graph সেটা গুঁড়িয়ে দেবে):
def dfs_iter(start, adj):
visited = {start}
stack = [start]
while stack:
node = stack.pop() # LIFO -> deep-first
for nxt in adj[node]:
if nxt not in visited:
visited.add(nxt)
stack.append(nxt)
return visited
একই visited set, একই O(V + E) cost, siblings-দের মধ্যে visiting order সামান্য আলাদা (explicit stack তাদের list-এর উল্টো order-এ try করে) — যা reachability, components, বা cycle detection-এর correctness-এ কখনোই matter করে না।
Connected components: DFS-এর signature move¶
"কতগুলো আলাদা islands / friend groups / networks?" — এখনো visit না হওয়া প্রতিটা node থেকে DFS চালাও; প্রতিটা launch ঠিক একটা গোটা component দখল করে।
def count_components(nodes, adj):
visited = set()
def dfs(node):
visited.add(node)
for nxt in adj[node]:
if nxt not in visited:
dfs(nxt)
count = 0
for node in nodes:
if node not in visited: # an unclaimed island!
dfs(node) # claim ALL of it
count += 1
return count
Mental model: একটা paint bucket। প্রতিটা top-level dfs(node) call এক রঙের রং ঢেলে দেয় যেটা connected সবকিছুতে ছড়িয়ে যায়; answer হলো কয়টা রঙ লাগল। (Number of Islands হলো এটাই, grid cells-কে nodes ধরে; Number of Provinces হলো এটাই, adjacency matrix দিয়ে; CSES Building Roads চায় components minus one।)
তিন রঙ দিয়ে cycle detection (directed graphs)¶
Directed graph-এ "already visited" দিয়ে cycle ঘোষণা করা যায় না — হতে পারে তুমি শুধু পুরোনো, শেষ-হয়ে-যাওয়া কোনো region-এ আবার পৌঁছেছ। সমাধান হলো node প্রতি তিনটা state:
WHITE = never touched
GRAY = currently on the recursion stack (we are INSIDE its exploration)
BLACK = fully finished (we have left it for good)
নিয়মটা: একটা GRAY node-এর সাথে দেখা হওয়া মানেই cycle। তুমি সামনে হেঁটে নিজেরই অসমাপ্ত পথের দাগে ধাক্কা খেয়েছ — current path-এর ভেতরে একটা loop। BLACK node-এর সাথে দেখা হওয়া নিরীহ: সেই রাস্তা পুরো explore হয়ে গেছে আর কোনো circular কিছুতে যায়নি।
WHITE, GRAY, BLACK = 0, 1, 2
def has_cycle(nodes, adj):
color = {node: WHITE for node in nodes}
def dfs(node):
color[node] = GRAY # entering: on the current path
for nxt in adj[node]:
if color[nxt] == GRAY: # ran into our own trail
return True
if color[nxt] == WHITE and dfs(nxt):
return True
color[node] = BLACK # leaving: fully explored
return False
return any(color[n] == WHITE and dfs(n) for n in nodes)
ঠিক এভাবেই Course Schedule "impossible" ঠিক করে: prerequisites-এর একটা cycle মানে কোনো valid study order নেই (আরও আছে topological-sort.md-এ)।
Undirected graph-এর জন্য test টা সহজ: DFS করতে করতে এমন কোনো visited neighbor দেখা যে সেই node না, যেখান থেকে এইমাত্র এলে — মানেই cycle। (অথবা DFS পুরোপুরি বাদ দিয়ে DSU ব্যবহার করো — ../10-disjoint-set-union/।)
Pre-order আর post-order: এক ঝলক, যেটা পরে কাজে দেবে¶
DFS-এ প্রতিটা node-এর দুটো timestamp থাকে:
- Pre-order (entry): DFS প্রথম যে মুহূর্তে পৌঁছায় — neighbors explore করার আগে।
- Post-order (exit): DFS যে মুহূর্তে ছেড়ে যায় — ALL neighbors পুরোপুরি explore হওয়ার পরে।
def dfs_orders(node, adj, visited, pre, post):
visited.add(node)
pre.append(node) # entering
for nxt in adj[node]:
if nxt not in visited:
dfs_orders(nxt, adj, visited, pre, post)
post.append(node) # leaving — everything below is done
কেন এটা পাত্তা দেবে? Post-order মানে "আমার সব dependents শেষ হয়ে গেছে।" একটা DAG-এর post-order উল্টে দাও, পেয়ে যাবে একটা valid topological order (topological-sort.md)। এই timestamp গুলোই পরে competitive programming-এ strongly connected components আর bridge-finding চালায় — DFS-এর exit times এই পুরো repo-র অন্যতম নীরব-শক্তিশালী idea।
(এগুলো ../07-trees/-এর tree traversals-এরই generalization: ওখানকার preorder আর postorder ছিল cycle-free graph-এ DFS-এর order।)
Flood fill: pixels-এ DFS¶
Image editor-এর paint-bucket tool টা আক্ষরিক অর্থেই DFS: একটা pixel থেকে শুরু করে তাকে recolor করো আর একই-রঙা neighbors-এ recurse করো।
def flood_fill(grid, r, c, new_color):
R, C = len(grid), len(grid[0])
old = grid[r][c]
if old == new_color: # crucial: avoid infinite re-painting
return grid
def dfs(r, c):
if 0 <= r < R and 0 <= c < C and grid[r][c] == old:
grid[r][c] = new_color # painting IS the visited-marking
for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
dfs(r + dr, c + dc)
dfs(r, c)
return grid
Elegance-টা খেয়াল করো: আলাদা কোনো visited set নেই — cell recolor করাটাই হলো mark। (Flood Fill হুবহু এটাই; Number of Islands হলো flood fill plus একটা counter; Pacific Atlantic Water Flow হলো ocean দুটো থেকে উল্টোদিকে চালানো দুটো flood fill।)
DFS vs BFS, এক নিঃশ্বাসে decision¶
DFS যখন প্রশ্নটা structure নিয়ে — components, cycles, orderings, "explore everything", backtracking-ধাঁচের searches। BFS যখন প্রশ্নটা distance নিয়ে। যেকোনোটা যখন নিছক reachability। (পুরো table bfs.md-এ।)
DFS-specific সাবধানতা:
- Recursion depth: একটা লম্বা path graph Python-এর stack overflow করায় — iterative-এ যাও, বা সাবধানে limit বাড়াও (
sys.setrecursionlimit), জেনে রেখো এটা একটা band-aid। - DFS খুঁজে পায় একটা path, shortest path না। "minimum steps"-এর জন্য DFS ব্যবহার করা হলো classic wrong-tool error।
- Flood fill-এ নিশ্চিত করো recoloring (বা visited-marking) recurse করার আগে হচ্ছে, নইলে identical-color region চিরকাল loop করে।
DFS-এর trigger words¶
"Connected components", "islands/regions/provinces", "detect a cycle", "is it possible to finish" (directed deps), "explore all", "flood fill", "all paths from A to B" (DFS + backtracking — দেখো ../06-recursion-and-backtracking/), "valid ordering" (DFS post-order route)।
Representative problems¶
- Number of Islands — grid-এ flood fill দিয়ে components।
- Clone Graph — DFS করতে করতে hash map-এ copies বানানো (inherits
../05-hashing/)। - Course Schedule — prerequisite digraph-এ GRAY/BLACK cycle detection।
- Pacific Atlantic Water Flow — দুই border থেকে reverse flood fill, তারপর reaches-এর intersection।
- CSES Building Teams — DFS (বা BFS) two-coloring; এক রঙের ভেতরে একটা edge মানেই impossible।
Reference treatment: cp-algorithms DFS। পরে: topological-sort.md, যেখানে DFS post-order তার প্রথম বড় payoff পায়।