Topological Sort — Dependencies-এর দুনিয়াকে Order করা¶
Data structure: directed graph + queue (Kahn) অথবা DFS post-order। Thinking tweak: যার আর কোনো prerequisite বাকি নেই, সেটা এখনই করা নিরাপদ।
Analogy: একটা recipe রান্না করা, একটা degree schedule করা¶
একটা recipe বলে: ডিম ফাটাও → ডিম ফেটাও → batter-এ মেশাও; oven preheat করো → bake করো। কিছু step অন্যদের আগে আসতেই হবে; অনেক জোড়ার কিছুই যায় আসে না (ডিম ফাটানোর আগে বা পরে — যখন খুশি preheat করতে পারো)। Topological order হলো এমন যেকোনো complete step list, যেটা কোনো arrow ভাঙে না।
একই shape: university-র courses। Calculus 1, তারপর Calculus 2, তারপর Calculus 3; Intro Programming, তারপর Data Structures। তোমার degree plan টা আসলে prerequisite graph-এর একটা topological sort।
Formal version: একটা directed graph দেওয়া আছে, nodes-গুলোকে এক লাইনে output করো যাতে প্রতিটা edge u → v-তে u আসে v-র আগে। মাথায় গেঁথে নেওয়ার দুটো fact:
- Order টা সাধারণত unique না — independent steps যেকোনো relative order-এ যেতে পারে। "A valid order", "the order" না।
- এটা exist করে iff graph-এ কোনো directed cycle নেই (একটা DAG)। "A requires B requires C requires A" কখনোই linearize করা যাবে না — cycle-টা একটা deadlock।
Kahn's algorithm: zero-indegree layer-টা ছাড়িয়ে নাও¶
কোনো node-এর indegree = ঢুকতে থাকা arrows-এর সংখ্যা = unmet prerequisites-এর সংখ্যা। Kahn-এর insight: indegree 0-ওয়ালা node-কে আটকানোর কিছুই নেই — এখনই করো। সেটা করলে তার outgoing arrows সরে যায়, যা নতুন nodes মুক্ত করতে পারে। Repeat।
from collections import deque
def topo_sort(nodes, adj):
indeg = {n: 0 for n in nodes}
for u in nodes:
for v in adj[u]:
indeg[v] += 1
q = deque(n for n in nodes if indeg[n] == 0) # everything doable NOW
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in adj[node]:
indeg[nxt] -= 1 # one prerequisite cleared
if indeg[nxt] == 0: # fully unblocked!
q.append(nxt)
return order if len(order) == len(nodes) else None # None = cycle
Cost: O(V + E) — প্রতিটা node একবার enqueue হয়, প্রতিটা edge একবার decrement হয়।
একটা course graph-এ queue-র frames¶
intro ──> ds ──> algo
│ ^
└────> math ────┘ (algo needs both ds and math)
indegrees: intro:0 ds:1 math:1 algo:2
Frame 0: queue = [intro] order = []
Frame 1: pop intro -> order=[intro]
ds: 1->0 (enqueue) math: 1->0 (enqueue)
queue = [ds, math]
Frame 2: pop ds -> order=[intro, ds]
algo: 2->1 queue = [math]
Frame 3: pop math -> order=[intro, ds, math]
algo: 1->0 (enqueue) queue = [algo]
Frame 4: pop algo -> order=[intro, ds, math, algo] queue empty. Done.
[intro, math, ds, algo]-ও সমানভাবে valid হতো — ds আর math পরস্পরকে constrain করে না। (Alphabetically smallest valid order চাও — একটা common competitive-programming twist? Queue-টা বদলে ../08-heap-priority-queue/-এর একটা min-heap বসাও।)
Cycle = queue-টা আগেভাগেই অনাহারে থাকে¶
Queue শুরুই হয় খালি অবস্থায়, order শেষ হয় 3-টার মধ্যে 0-টা node নিয়ে, আর length check টা None return করে। আংশিক cyclic graph-এ acyclic অংশটা process হয়ে যায় আর cycle-এর সদস্যরা কখনোই indegree 0-তে পৌঁছায় না — len(order) < len(nodes) হলো universal cycle alarm। ঠিক এভাবেই Course Schedule "possible?" এর উত্তর দেয় আর Course Schedule II plan-টা produce করে।
DFS alternative: উল্টানো post-order¶
dfs.md থেকে: কোনো node-এর post-order timestamp বাজে কেবল তখন, যখন তার থেকে reachable সবকিছু পুরোপুরি explore হয়ে গেছে। তাই একটা DAG-এ যেকোনো edge u → v-র জন্য, v finish করে u-র আগে — মানে finish order টা হলো একটা valid topological order, উল্টো করে।
def topo_sort_dfs(nodes, adj):
WHITE, GRAY, BLACK = 0, 1, 2
color = {n: WHITE for n in nodes}
out = []
def dfs(node):
color[node] = GRAY
for nxt in adj[node]:
if color[nxt] == GRAY: # back edge: cycle
return False
if color[nxt] == WHITE and not dfs(nxt):
return False
color[node] = BLACK
out.append(node) # POST-order: appended when finished
return True
for n in nodes:
if color[n] == WHITE and not dfs(n):
return None # cycle found
return out[::-1] # reverse the finish order
একই O(V + E), একই cycle detection (dfs.md-এর GRAY trick)। কোনটা ব্যবহার করবে?
| Kahn (BFS-style) | DFS post-order | |
|---|---|---|
| Mental model | unblocked nodes-কে layer by layer ছাড়িয়ে নাও | dependents শেষ করো, তারপর নিজের নাম ঘোষণা করো |
| Cycle signal | output V-এর চেয়ে ছোট | একটা GRAY node-এর সাথে দেখা |
| Easy extras | lexicographic order (heap), প্রতিটা task-এর "level" | পরের algorithms-এর জন্য preorder/postorder timestamps |
| Recursion risk | নেই | গভীর graph overflow করতে পারে (iterative-এ যাও) |
দুটোই interview-standard; একটা পুরোপুরি ঠোঁটস্থ রাখো, অন্যটা sketch করার মতো ভালোভাবে জানো।
DP-on-DAG teaser¶
Topological order শুধু একটা scheduling-এর উত্তর না — এটা graph-এ dynamic programming-এর একটা নিরাপদ processing order। Topo order-এ nodes process করো, তাহলে node v-তে পৌঁছানোর সময় প্রতিটা predecessor-এর answer ইতিমধ্যেই final:
# longest path ending at each node of a DAG (impossible on cyclic graphs!)
longest = {n: 0 for n in nodes}
for u in topo_order:
for v in adj[u]:
longest[v] = max(longest[v], longest[u] + 1)
Paths গোনা, DAG-এ negative weights সহ shortest paths, project-duration (critical path) calculation — সবই একটা topological order-এর উপর এক relaxation loop। পরে এই repo-তে dynamic programming-এ পৌঁছালে মনে রেখো: DP-র "solve subproblems first" আসলে subproblems-এর মধ্যকার dependency graph-এর একটা topological order। যে idea-টা এইমাত্র শিখলে, সেটাই চুপচাপ পুরো DP-র নিচে শুয়ে আছে।
Common mistakes (সাধারণ ভুল)¶
- Undirected graph-এ topological sort চালানো — concept-টা শুধু directed graph-এর জন্যই exist করে।
- শেষের
len(order) == len(nodes)check টা ভুলে যাওয়া — cyclic input তখন নিঃশব্দে একটা অসম্পূর্ণ "order" দেয়। - Edges উল্টো বানানো: "course A requires B" মানে edge B → A (B unlock করে A-কে)। উল্টানো edges একটা নিখুঁত valid reverse schedule produce করে — classic silent bug।
- DFS post-order list উল্টাতে ভুলে যাওয়া।
- Output unique ধরে নিয়ে tests-এ একটা expected order hard-code করা।
Trigger words¶
"Prerequisites", "dependencies", "build/install order", "schedule with constraints", "must come before", "is it possible to finish everything", "derive an ordering from constraints" (Alien Dictionary), "longest chain of dependent tasks"।
Representative problems¶
- Course Schedule — শুধু cycle detection ("কোনো order possible?")।
- Course Schedule II — আসল order-টা produce করো; প্রায় হুবহু Kahn।
- CSES Course Schedule — scale-এ competitive-programming version।
- Alien Dictionary — আগে sorted words থেকে constraint graph বানাও, তারপর topo-sort করো; sorting-এর চেয়ে বেশি modeling পরীক্ষা করে।
- Longest Increasing Path in a Matrix — increasing moves-এর implicit DAG-এ DP।
Reference treatment: cp-algorithms topological sort। Course-graph dry run সহ runnable Kahn আছে implementation.py-তে। চারটা theory file পড়া শেষ — এবার তুমি problems/README.md-এর জন্য তৈরি।