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