ট্যোপোলজিকাল সর্ট একটি DAG (directed acyclic graph) এর শীর্ষবিন্দুগুলিকে রৈখিকভাবে সাজায় যাতে প্রতিটি edge u->v এ u আগে থাকে v। এটি উত্তর দেয় "এই কাজগুলি তাদের নির্ভরতা দেওয়া অবস্থায় কোন ক্রমে করতে পারি?"
দুটি সাধারণ পদ্ধতি: (বারবার in-degree 0 সহ নোড সরান) অথবা (রিভার্স post-order)। একটি বৈধ সাজান ।
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
বিল্ড সিস্টেম, কাজের সময়সূচী, কোর্স পূর্বশর্ত এবং নির্ভরতা সমাধানের জন্য ব্যবহার করুন। যদি ফলাফল V এর চেয়ে ছোট হয়, গ্রাফের একটি চক্র আছে (কোনো বৈধ ক্রম নেই)। সাজান সাধারণত অনন্য নয়।
নির্ভরতা ক্রমায়ন সর্বত্র রয়েছে — কম্পাইলার, প্যাকেজ ম্যানেজার, স্প্রেডশীট পুনর্গণনা, CI পাইপলাইন।
ট্যোপোলজিকাল সর্ট ডাইরেক্টেড গ্রাফের জন্য চক্র সনাক্তকরণ হিসাবেও কাজ করে।
একটি সমস্যাকে "সীমাবদ্ধতার অধীনে ক্রমায়ন" হিসাবে স্বীকৃতি দেওয়া এবং topo sort এর জন্য পৌঁছানো একটি শক্তিশালী সিনিয়র সংকেত।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন