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

ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search - BFS)

শহরের ম্যাপে লেভেল বা রিং ধরে খোঁজা — কাছের বন্ধুরা আগে

time: O(V+E)space: O(V)

ধরুন আপনি রাস্তার ম্যাপ হাতে শহর A-তে দাঁড়িয়ে আছেন। আপনার টার্গেট হলো বাকি সব শহরে যানয়ার সবচেয়ে ছোট রাস্তা বা শর্টেস্ট রুট খুঁজে বের করা। আপনার প্ল্যানটা এমন: প্রথমে A-এর সাথে সরাসরি যে শহরগুলোর কানেকশন আছে, সেগুলোতে যাবেন। এরপর সেই শহরগুলোর সাথে যাদের কানেকশন আছে, সেখানে যাবেন। তারপর তার পরের লেভেলে... এভাবে ধীরে ধীরে বৃত্ত বা রিং বড় করতে থাকবেন।

এই যে বৃত্ত বা রিং ধরে ধরে ধীরে ধীরে ম্যাপের পরিধি বাড়ানোর সিস্টেম, এটার গালভরা নামই হলো ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search বা BFS)। এটা আগে ১ দূরত্বে (distance) থাকা সব শহর ঘুরে দেখে, তারপর ২ দূরত্বে থাকা শহরগুলো ধরে, তারপর ৩... এভাবেই চলতে থাকে।

এখানে আসল হিরো হলো কিউ (Queue)

BFS করার জন্য একটা কিউ (Queue) লাগে — যেটা হলো বাসের লাইনের মতো, যে আগে আসবে সে আগে সার্ভিস পাবে (First-in, First-out)। যেসব শহরে এখনো যানয়া হয়নি, তারা এই লাইনে সিরিয়াল দিয়ে দাঁড়ায়। লাইনের একদম সামনে যে শহরটা থাকে, সেটাকে প্রথমে প্রসেস করা হয়। তারপর তার সাথে রাস্তা দিয়ে যুক্ত যেসব শহরে বা প্রতিবেশীর কাছে এখনো যানয়া হয়নি, তাদের সবাইকে ধরে এনে ওই লাইনের একদম পেছনে দাঁড় করিয়ে দেওয়া হয়।

pseudocode

function bfs(graph, start):
  queue = [start]
  visited = {start}

  while queue is not empty:
    city = queue.shift()          // সামনের জনকে লাইন থেকে বের করুন
    process(city)

    for neighbor of graph[city]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.push(neighbor)      // প্রতিবেশীদের লাইনের পেছনে দাঁড় করান

BFS কেন সবচেয়ে ছোট রাস্তা (Shortest Path) বের করতে পারে?

কারণ BFS সবসময় শুরু থেকে দূরত্বের সিরিয়াল ধরে শহরগুলো ভিজিট করে। তাই BFS যখন প্রথমবার কোনো শহরে পৌঁছায়, আপনি চোখ বন্ধ করে বলতে পারেন যে সে সবচেয়ে ছোট রাস্তা বা শর্টেস্ট রুট ধরেই সেখানে গেছে — কারণ সে বড় রাস্তার শহরগুলোতে যানয়ার আগে ছোট রাস্তার সব কাজ শেষ করে তবেই এগোয়।

তবে মনে রাখবেন, এই জাদুটা কিন্তু শুধু আনওয়েটেড গ্রাফের (Unweighted graph) ক্ষেত্রেই খাটে। যদি রাস্তাগুলোর দূরত্ব বা খরচ আলাদা আলাদা (Weighted) হয়, তখন আর এটা দিয়ে কাজ হবে না; সেটার জন্য আপনাকে ডাইকস্ট্রা (Dijkstra) অ্যালগরিদম ব্যবহার করতে হবে।

লেভেল-অর্ডার ট্রাভার্সাল (Level-order traversal)

আসলে BFS স্বাভাবিকভাবেই একটা লেভেল-অর্ডার ট্রাভার্সাল জন্ম দেয়। লেভেল ০ মানে হলো শুরুর নোডটা একা। লেভেল ১ মানে হলো তার সরাসরি প্রতিবেশীরা। লেভেল ২ হলো প্রতিবেশীদের প্রতিবেশীরা। একটা লেভেলের বা লাইনের সবার কাজ শেষ করে যখন নতুন লেভেলের কাজ শুরু হয়, তখন আপনি চাইলে হিসাব রাখতে পারেন যে আপনি কত নম্বর লেভেলে আছেন।

◈ BFS-কে কাজ করতে দেখুন

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

দ্রষ্টব্য: আনওয়েটেড বা ওজন ছাড়া গ্রাফে BFS শর্টেস্ট রুটের ১০০% গ্যারান্টি দেয়। কিউ এখানে লেভেল বা তলা মেইনটেইন করার দায়িত্ব পালন করে — অর্থাৎ d দূরত্বের সবার কাজ শেষ না হওয়া পর্যন্ত সে কখনোই কাউকে d+1 দূরত্বে পৌঁছাতে দেয় না।