ডেটা স্ট্রাকচারে গ্রাফ সার্চিং

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

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

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

ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল একটি অ্যালগরিদম যা একটি প্রদত্ত গ্রাফের সকল নোড দখল করতে ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড নির্বাচন করা হয় এবং তারপর সব সন্নিহিত নোডগুলো একেক করে দখল করা হয়। সব সন্নিহিত ভেরটেক্স সম্পন্ন হলে, এটি অন্য একটি ভেরটেক্সে যায় এবং আবার তার সন্নিহিত ভেরটেক্সগুলো চেক করে। এই অ্যালগরিদম বাস্তবায়ন করতে কিউ ডেটা স্ট্রাকচার ব্যবহার করতে হয়। সব সন্নিহিত ভেরটেক্স কিউতে যোগ করা হয় এবং যখন সব সন্নিহিত ভেরটেক্স সম্পন্ন হয়, একটি আইটেম কিউ থেকে সরিয়ে সেটি থেকে আবার ট্রাভার্সাল শুরু করা হয়।

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

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

DFS ইটারেটিভভাবে বাস্তবায়ন করতে স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হয়। যদি রিকার্সিভভাবে করতে চাই, তবে এক্সটার্নাল স্ট্যাক দরকার নেই, রিকার্শন কলের জন্য ইন্টার্নাল স্ট্যাক ব্যবহার করা হয়।