Topological Sort

এমন একটি order বানান যেখানে প্রতিটি task তার dependency-গুলোর পরে আসে।

মূল ধারণা (জামাকাপড় পরা)

মোজার আগে জুতা পরা যায় না, শার্টের আগে জ্যাকেটও না। প্রতিটি arrow A → B মানে "A আগে হতে হবে, B পরে"। Topological sort সবকিছুকে এমন order-এ সাজায় যা প্রতিটি arrow মেনে নেয়। কোর্সের prerequisite, build system আর task scheduler, সবখানেই এটা লাগে।

Kahn’s algorithm কাজটা করে বারবার এমন কিছু করে যা এখনই করা যায়:

  1. প্রতিটি task-এর জন্য গুনুন সে এখনো কয়টি জিনিসের অপেক্ষায় আছে। এই সংখ্যাকে বলে indegree (যতগুলো arrow তার দিকে আসছে)।
  2. যে task-এর indegree 0, সে কারো জন্য অপেক্ষা করছে না। তাদের queue-তে রাখুন।
  3. Queue থেকে একটি task নিয়ে answer-এ যোগ করুন। তারপর তার arrow গুলো "কেটে দিন": যেসব task তার জন্য অপেক্ষা করছিল, তাদের অপেক্ষার সংখ্যা এক কমে যায়। কোনো task 0 হলে তাকে queue-তে রাখুন।

যদি নেওয়ার মতো task শেষ হয়ে যায় কিন্তু কিছু task তখনও অপেক্ষায় থাকে, তাহলে তারা একে অপরের জন্য অপেক্ষা করছে: এটাই cycle, আর কোনো valid order নেই।

Run করে দেখুন

Task গুলোর নম্বর 0 থেকে শুরু। সর্বোচ্চ 15টি arrow।

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: প্রতিটি task সর্বোচ্চ একবার queue-তে ঢোকে আর প্রতিটি arrow একবার কাটা হয়, তাই সময় প্রায় task আর arrow-এর যোগফলের সমান (O(V + E))।