এমন একটি order বানান যেখানে প্রতিটি task তার dependency-গুলোর পরে আসে।
মূল ধারণা (জামাকাপড় পরা)
মোজার আগে জুতা পরা যায় না, শার্টের আগে জ্যাকেটও না। প্রতিটি arrow A → B মানে "A আগে হতে হবে, B পরে"। Topological sort সবকিছুকে এমন order-এ সাজায় যা প্রতিটি arrow মেনে নেয়। কোর্সের prerequisite, build system আর task scheduler, সবখানেই এটা লাগে।
Kahn’s algorithm কাজটা করে বারবার এমন কিছু করে যা এখনই করা যায়:
প্রতিটি task-এর জন্য গুনুন সে এখনো কয়টি জিনিসের অপেক্ষায় আছে। এই সংখ্যাকে বলে indegree (যতগুলো arrow তার দিকে আসছে)।
যে task-এর indegree 0, সে কারো জন্য অপেক্ষা করছে না। তাদের queue-তে রাখুন।
Queue থেকে একটি task নিয়ে answer-এ যোগ করুন। তারপর তার arrow গুলো "কেটে দিন": যেসব task তার জন্য অপেক্ষা করছিল, তাদের অপেক্ষার সংখ্যা এক কমে যায়। কোনো task 0 হলে তাকে queue-তে রাখুন।
যদি নেওয়ার মতো task শেষ হয়ে যায় কিন্তু কিছু task তখনও অপেক্ষায় থাকে, তাহলে তারা একে অপরের জন্য অপেক্ষা করছে: এটাই cycle, আর কোনো valid order নেই।
Run করে দেখুন
Task গুলোর নম্বর 0 থেকে শুরু। সর্বোচ্চ 15টি arrow।
নিজে চেষ্টা করুন
Default input run করুন। একাধিক valid order থাকতে পারে; এটা queue-র বেছে নেওয়া order। দেখুন answer-এ প্রতিটি arrow সামনের দিকে যায় কি না।
1>5-এর মতো একটা arrow যোগ করুন যা loop বানায়। কী হয়, আর কোন node গুলো আটকে যায়?
সব arrow মুছে দিন। task গুলো কোন order-এ বের হয়?
একটা সরল chain বানান 0>1, 1>2, 2>3। কয়টি valid order আছে?
সাধারণ ভুল
cycle check না করা।len(order) != n হলে input-এ cycle আছে, আর আংশিক order না দিয়ে সেটাই report করতে হবে।
arrow-এর দিক গুলিয়ে ফেলা। code লেখার আগে ঠিক করুন "A→B" মানে কী ("A আগে B-র" নাকি "B-র A লাগে")। অনেক course problem-এ pair দেওয়া থাকে [course, prerequisite] আকারে, যা উল্টো।
বিচ্ছিন্ন node ভুলে যাওয়া। যেসব task-এ কোনো arrow নেই তাদের indegree 0, এবং তাদেরও answer-এ আসতে হবে।
ধরে নেওয়া যে answer একটাই। সাধারণত অনেক valid order থাকে। test-এ একটি নির্দিষ্ট list নয়, order valid কি না সেটা check করুন।
Complexity, সহজ ভাষায়: প্রতিটি task সর্বোচ্চ একবার queue-তে ঢোকে আর প্রতিটি arrow একবার কাটা হয়, তাই সময় প্রায় task আর arrow-এর যোগফলের সমান (O(V + E))।