BFS (Breadth-First Search)
BFS (Breadth-First Search) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি গ্রাফের সমস্ত ভেরটেক্স এবং এজকে স্তর-বাই-স্তর ভিজিট করে। এটি একটি নোডের সব প্রতিবেশী নোডকে প্রথমে ভিজিট করে, তারপর তাদের প্রতিবেশী নোডগুলোকে ভিজিট করতে চলে যায়। BFS সাধারণত সারি (queue) ব্যবহার করে কাজ করে।
BFS অ্যালগরিদমের ধাপ:
- প্রাথমিক ভেরটেক্স নির্বাচন: BFS শুরু করার জন্য একটি প্রাথমিক ভেরটেক্স নির্বাচন করুন এবং এটিকে ভিজিট করুন।
- সারিতে ভেরটেক্স যোগ করুন: প্রাথমিক ভেরটেক্সটি সারিতে (queue) যোগ করুন।
- নোড ভিজিট করা:
- যখন সারি খালি না হয়, তখন:
- প্রথম ভেরটেক্সটি বের করুন এবং এটিকে ভিজিট করুন।
- বের করা ভেরটেক্সের সমস্ত প্রতিবেশী নোডগুলিকে চেক করুন:
- যদি প্রতিবেশী নোডটি পূর্বে ভিজিট করা না হয়ে থাকে, তবে এটিকে সারিতে যোগ করুন এবং ভিজিট করা হিসাবে চিহ্নিত করুন।
- যখন সারি খালি না হয়, তখন:
- পুনরাবৃত্তি: উপরের ধাপগুলি পুনরাবৃত্তি করুন যতক্ষণ না সারি খালি হয়ে যায়।
পseudocode for BFS
উদাহরণ
ধরি, আমাদের একটি গ্রাফ আছে:
BFS-এ আউটপুট হবে:
- শুরু করি A থেকে।
- A এর প্রতিবেশী B এবং C কে সারিতে যোগ করি।
- B বের করার পর, D এবং E কে সারিতে যোগ করি।
- C বের করার পর, F কে সারিতে যোগ করি।
- শেষ পর্যন্ত D, E, F কে ভিজিট করি।
BFS-এর সুবিধা
- সর্বনিম্ন পথ খোঁজা: BFS একটি গ্রাফের মধ্যে দুই ভেরটেক্সের মধ্যে সর্বনিম্ন দূরত্ব খুঁজে পেতে কার্যকরী।
- স্তর বিশ্লেষণ: BFS গ্রাফের স্তরভিত্তিক বিশ্লেষণে সহায়ক। এটি বিভিন্ন ভেরটেক্সের স্তর বোঝাতে সাহায্য করে।
- সোজা বাস্তবায়ন: সারি ব্যবহার করে সহজে বাস্তবায়ন করা যায়।
BFS-এর অসুবিধা
- মেমরি ব্যবহার: BFS বড় গ্রাফের ক্ষেত্রে অনেক মেমরি ব্যবহার করতে পারে, কারণ সারিতে সব ভিজিট হওয়া নোডগুলিকে রাখতে হয়।
- স্পর্শকাতর সমস্যা: যদি গ্রাফের গঠন অনেক স্তরের হয় তবে এটি ধীর গতিতে কাজ করতে পারে।
সারসংক্ষেপ
BFS (Breadth-First Search) হল একটি শক্তিশালী গ্রাফ ট্রাভার্সাল অ্যালগরিদম, যা স্তর-বাই-স্তর ভিত্তিতে নোডগুলি ভিজিট করে। এটি সর্বনিম্ন পথ খোঁজার জন্য কার্যকরী এবং গ্রাফের স্তর বিশ্লেষণে সহায়ক। BFS বাস্তবায়ন করা সহজ এবং বিভিন্ন বাস্তব জীবনের সমস্যার সমাধানে ব্যবহৃত হয়।
Content added By
