Topological Sort

টপোলজিক্যাল সর্ট

একটা DAG-এর vertex-দের এমন ক্রমে সাজানো যাতে প্রতিটা edge আগের থেকে পরের দিকে যায়। DAG হলে সম্ভব, নাহলে নয়।

also: toposort, topological ordering

Theorem: topological sort আছে যদি এবং কেবল যদি graph একটা DAG।

চক্র থাকলে (A → B → C → A) A-কে A-এর আগে রাখতে হতো। অসম্ভব।

Kahn’s algorithm — O(V + E):

ready = deque(n for n in nodes if indeg[n] == 0)
while ready:
    u = ready.popleft(); order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0: ready.append(v)
if len(order) != len(nodes): raise ValueError("চক্র আছে")

একাধিক বৈধ ক্রম থাকতে পারে — আর সেটাই সুবিধা। একই indeg == 0 স্তরের সব task সমান্তরালে চালানো যায়।

যেখানে চলছে: make, Bazel, apt, cargo, npm, Excel-এর recalculation, compiler-এর instruction scheduling, Kubernetes init container, আর এই ওয়েবসাইটের কারিকুলাম roadmap — studyOrder() আক্ষরিকভাবে এই algorithm চালায়।

Cycle detection ব্যর্থতার বার্তায় কোন চক্র সেটা বলা জরুরি — DFS-এর তিন-রঙ (white/gray/black) পদ্ধতিতে back edge ধরে পথটা পুনর্গঠন করা যায়।