গ্রাফপড়তে ৫ মিনিট লাগবে

টপোলজিক্যাল সর্ট (Topological Sort)

শহরগুলোকে এমনভাবে সাজান যেন সব ওয়ান-ওয়ে রাস্তা শুধু সামনের দিকেই যায়, পেছনের দিকে নয়

Kahn's: O(V+E)DFS-based: O(V+E)space: O(V)

এমন একটা শহরের ম্যাপের কথা ভাবুন, যেখানে সব রাস্তাই ওয়ান-ওয়ে (One-way) এবং ঘুরেফিরে আগের জায়গায় আসার কোনো রাস্তা বা চক্কর নেই। এই ধরনের ম্যাপকে বলা হয় Directed Acyclic Graph (DAG) (একটা গ্রাফ হিসেবে সেভ করা)। এখন আপনি শহরগুলোকে এমন একটা সিরিয়ালে সাজাতে চান, যেন যেকোনো ওয়ান-ওয়ে রাস্তা আপনার লিস্টের আগের কোনো শহর থেকে শুধু পরের কোনো শহরের দিকেই যায় (কখনোই উল্টোটা নয়)।

এভাবে সাজানেনটাকেই বলা হয় টপোলজিক্যাল সর্ট (Topological sort)। সহজ কথায়, এটা হলো: "যখন কিছু কাজ করার আগে অন্য কিছু কাজ আগেভাগে করাটা বাধ্যতামূলক (prerequisites), তখন কোন সিরিয়ালে কাজগুলো করা উচিত?" — যেমন ভার্সিটির কোর্স নেওয়া (আগে বেসিক, তারপর অ্যাডভান্সড), সফটওয়্যার বিল্ড করা, বা রান্নার রেসিপির ধাপগুলো ফলো করা।

কানের অ্যালগরিদম (Kahn's Algorithm - BFS নির্ভর)

এর আসল ট্রিকটা হলো: যে শহরে ঢোকার জন্য বাইরে থেকে কোনো রাস্তা আসেনি (in-degree = 0), তাকে সবার আগে লিস্টে বসানো যায় — কারণ তার আগে অন্য কোনো শহরে যানয়ার কোনো শর্ত বা বাধ্যবাধকতা নেই। তাকে লিস্টে বসিয়ে ম্যাপ থেকে সরিয়ে দিন। এর ফলে হয়তো ওর আশপাশের কিছু শহরেরও এখন আর বাইরের কোনো রাস্তা (in-degree) বাকি থাকল না। এবার তাদের নিয়ে সেম কাজটা বারবার করতে থাকুন।

pseudocode

function kahnSort(graph):
  inDegree = প্রতিটা শহরে ঢোকার কয়টা রাস্তা আছে তার হিসাব
  queue = এমন সব শহর যাদের ইন-ডিগ্রি বা ঢোকার রাস্তা 0
  order = []

  while queue ফাঁকা না হয়:
    city = queue.shift()
    order.push(city)
    for neighbor of graph[city]:
      inDegree[neighbor]--
      if inDegree[neighbor] === 0:
        queue.push(neighbor)

  // যদি order.length < V হয়, তার মানে ম্যাপে কোনো গোলকধাঁধা বা সাইকেল ছিল!
  return order

DFS-ভিত্তিক অ্যালগরিদম

DFS চালানো শুরু করুন। যখন একটা শহরের সবদিক পুরোপুরি ঘোরা হয়ে যাবে (অর্থাৎ ওই শহর থেকে বের হওয়া সব রাস্তার কাজ শেষ), তখন তাকে একটা স্ট্যাকে (stack) ঢুকিয়ে রাখুন। সব কাজ শেষ হলে, স্ট্যাক থেকে এক এক করে শহরগুলোকে বের করে আনলেই আপনি টপোলজিক্যাল সিরিয়াল পেয়ে যাবেন। যেই শহরগুলোর কাজ সবার শেষে শেষ হয়েছে, তারা লিস্টের একদম শুরুতে বসবে — কারণ তাদের ওপর অন্য কারোর নির্ভরতা (dependencies) নেই।

pseudocode

function dfsTopoSort(graph):
  visited = {}
  stack = []

  function dfs(city):
    visited[city] = true
    for neighbor of graph[city]:
      if not visited[neighbor]: dfs(neighbor)
    stack.push(city)  // আশপাশের সব কাজ শেষ হলে তারপর স্ট্যাকে ঢোকান

  for each city: if not visited: dfs(city)
  return stack.reverse()

বোনাস কাজ: সাইকেল বা চক্কর ধরা

কানের (Kahn's) অ্যালগরিদম শুধু সর্টিংই করে না, সাইকেল বের করারও দারুণ একটা টুল: যদি সর্ট করার পর দেখা যায় লিস্টে মোট শহরের সংখ্যা ম্যাপের আসল শহরের (V) চেয়ে কম, তার মানে হলো—বাকি শহরগুলো এমন একটা চক্কর বা সাইকেলের মধ্যে আটকে আছে যাদের ইন-ডিগ্রি (in-degree) কখনোই 0 হতে পারেনি। আর সাইকেল থাকলে টপোলজিক্যাল সর্ট করা একেবারেই অসম্ভব।

◈ Watch topological sort

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: টপোলজিক্যাল সর্ট শুধুমাত্র সেই ম্যাপগুলোতেই কাজ করে যেগুলো DAG (Directed Acyclic Graphs)। যদি ম্যাপের ভেতরে কোনো সাইকেল বা চক্রাকার রাস্তা থাকে — তবে তাদের কোনো ভ্যালিড বা সঠিক সিরিয়ালে সাজানেন সম্ভব নয়।