ডেটা স্ট্রাকচারে একটি গ্রাফ অনুসন্ধান করা

আমরা জানি যে গ্রাফ হল একটি নন-লিনিয়ার ডেটা স্ট্রাকচার। এই ডেটা স্ট্রাকচারে, আমরা নোডগুলিতে কিছু মান রাখি এবং নোডগুলি বিভিন্ন প্রান্তে সংযুক্ত থাকে। আমরা যেমন গ্রাফ কাঠামোতে ডেটা সঞ্চয় করতে পারি, সেহেতু সেগুলি ব্যবহার করার জন্য আমাদের গ্রাফ থেকে উপাদানগুলি অনুসন্ধান করতে হবে৷

গ্রাফে অনুসন্ধানের জন্য, দুটি ভিন্ন পদ্ধতি রয়েছে। দ্য ব্রেডথ ফার্স্ট সার্চ এবং ডেপথ ফার্স্ট সার্চিং কৌশল।

ব্রেডথ ফার্স্ট সার্চ (BFS)

ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল হল একটি অ্যালগরিদম, যা একটি প্রদত্ত গ্রাফের সমস্ত নোড দেখার জন্য ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড নির্বাচন করা হয় এবং তারপরে পার্শ্ববর্তী সমস্ত নোডগুলি একে একে পরিদর্শন করা হয়। সমস্ত সংলগ্ন শীর্ষবিন্দুগুলি সম্পূর্ণ করার পরে, এটি অন্য শীর্ষবিন্দু পরীক্ষা করতে আরও এগিয়ে যায় এবং এর সন্নিহিত শীর্ষগুলি আবার পরীক্ষা করে। এই অ্যালগরিদম বাস্তবায়ন করতে, আমাদের সারি ডেটা কাঠামো ব্যবহার করতে হবে। সমস্ত সংলগ্ন শীর্ষবিন্দু সারিতে যোগ করা হয় যখন সমস্ত সন্নিহিত শীর্ষবিন্দু সম্পূর্ণ হয়, একটি আইটেম সারি থেকে সরানো হয় এবং আবার সেই শীর্ষবিন্দুর মধ্য দিয়ে যেতে শুরু করে৷

ডেপথ ফার্স্ট সার্চ (DFS)

দ্য ডেপথ-ফার্স্ট সার্চ (DFS) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম৷ এই অ্যালগরিদমে, একটি প্রারম্ভিক শীর্ষবিন্দু দেওয়া হয় এবং যখন একটি সংলগ্ন শীর্ষবিন্দু পাওয়া যায়, এটি প্রথমে সেই সন্নিহিত শীর্ষে চলে যায় এবং একই পদ্ধতিতে অতিক্রম করার চেষ্টা করে। এটি পুরো গভীরতার মধ্য দিয়ে চলে, যতটা যেতে পারে, তার পরে এটি নতুন পথ খুঁজে পেতে পূর্ববর্তী শীর্ষবিন্দুতে পৌঁছাতে পিছিয়ে যায়।

পুনরাবৃত্ত উপায়ে DFS বাস্তবায়ন করতে, আমাদের স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হবে। আমরা যদি এটি পুনরাবৃত্তভাবে করতে চাই, বহিরাগত স্ট্যাকের প্রয়োজন নেই, এটি পুনরাবৃত্তি কলের জন্য অভ্যন্তরীণ স্ট্যাক করা যেতে পারে।