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

নিচের অ্যানিমেশনটা দেখি, ডেপথ ফার্স্ট সার্চ কিভাবে হয়, তার ভিজুয়াল চিত্রঃ

ডেপথ ফার্স্ট সার্চ কিভাবে হয়, তার ভিজুয়াল চিত্র। সোর্সঃ উইকিপিডিয়া
ডেপথ ফার্স্ট সার্চ করার জন্য আমরা ব্যবহার করি Stack ডেটা স্ট্র্যাকচার। Stack হচ্ছে Last In First Out ডেটা স্ট্রাকচার। আনফেয়ার ডেটা স্ট্রাকচারও বলতে পারেন। স্ট্যাকের উদাহরণ হচ্ছে খাবারের প্লেট গুলো। প্লেট যেটা সবার আগে রাখা হয়, সেটা থাকে সবার নিচে। যেটা একবারে শেষে রাখা হয়, সেটা থাকে সবার উপরে। এবং আমরা সাধারনত সবার উপরেরটাই সবার আগে নেই।

Depth-First Search Traversal:
আমরা নিচের গ্রাফটি ডেপথ ফার্স্ট সার্চ অ্যালগরিদমের সাহায্যে ভ্রমন করব।

এ জন্য প্রথমে আমরা রুট নড বা ইনিশিয়াল নড দিয়ে শুরু করব। যেমন 1 হচ্ছে আমাদের রুট নড। এটাকে স্ট্যাকে ঢুকাবো। তাহলে স্ট্যাকে থাকে শুধু 1।

দেখব এক থেকে এর পর যাওয়া যায় 2 তে। স্ট্যাকে 2 ঢুকাবো। 2 থেকে যাওয়া যায় 3 এ। স্ট্যাকে 3 ঢুকাবো। 3 থেকে যাওয়া যায় 4 এ। স্ট্যাকে 4 ঢুকাবো। 4 থেকে আর কোথাও যাওয়া যায় না। স্ট্যাকে থাকবে 1,2,3,4।

চার থেকে যেহেতু আর কোথাও যাওয়া যায় না, আমরা 4 কে স্ট্যাক থেকে বের করব। বের করে ভিজিটেড লিস্টে রাখব। এখন স্ট্যাকের সবার উপরে থাকবে 3। 3 থেকে দেখব কোথায় যাওয়া যায়। 3 থেকে চার এ যাওয়া যায়। 4 আমাদের ভিজিটেড লিস্টে রয়েছে। তাই 4 এ আর ভিজিট করব না। এ ছাড়া 3 থেকে আর কোথাও যাওয়া যায়? যায় না। তাহলে 3 স্ট্যাক থেকে রিমুভ করব। এবং 3 কে ভিজিটেড লিস্টে রাখব। তাহলে স্ট্যাকে থাকবে 1,2।

এখন স্ট্যাকে সবার উপরে যেহেতু 2 থাকবে, আমরা দেখব দুই থেকে প্রথমে কোথায় যাওয়া যায়। দেখব 3 এ যাওয়া যায়। 3 এ আমরা এর আগে একবার গিয়েছি। তাই 3 ছাড়া দেখব আর কোথায় যাওয়া যায়। আর কোথাও যাওয়া যায় না। তাহলে 2কে স্ট্যাক থেকে রিমুভ করব এবং ভিজিটেড লিস্টে রাখব। স্ট্যাকে এখন রয়েছে শুধু 1।

1 থেকে সবার আগে কোথায় যাওয়া যায়? 2 এ। 2 আমরা ভিজিট করেছি। এরপর যাওয়া যায় 5 এ। তাহলে 5 কে স্ট্যাকে ঢুকাবো। 5 থেকে এরপর আগে যাওয়া যায় 6 এ। 6 কে স্ট্যাকে ঢুকাবো। 6 থেকে যাওয়া যায় 7 এ। 7 কে স্ট্যাকে ঢুকাবো। 7 থেকে আর কোথাও যাওয়া যায় না। যেহেতু 7 থেকে আর কোথাও যাওয়া যায় না, তাই আমরা 7 কে স্ট্যাক থেকে রিমুভ করব এবং ভিজিটেড লিস্টে রাখব। তাহলে আমাদের স্ট্যাকে এখন থাকবেঃ 1,5,6

স্ট্যাকের এখন সবার উপরে থাকবে 6। 6 থেকে যেহেতু আর কোথাও যাওয়া যায় না, আমরা 6 কে স্ট্যাক থেকে রিমুভ করব এবং ভিজিটেড লিস্টে রাখব। এখন স্ট্যাকে থাকবে 1,5।

5 ভিজিট করে দেখব 5 থেকে আর কোথাও যাওয়া যায়? হ্যা, যাওয়া যায়। 5 থেকে 6 এ যাওয়া যায়। কিন্তু 6 আমরা একবার ভিজিট করেছি। এরপর আর যাওয়া যায়? হ্যা, 5 থেকে এরপর 8 এ যাওয়া যায়। তাহলে আমরা স্ট্যাকে 8 ঢুকাবো। এখন স্ট্যাকে থাকবে 1,5,8। এভাবে এরপরের নড গুলো আমরা ভিজিট করব।

ডেপথ ফার্স্ট সার্চ এর ব্যবহারঃ সাধারণত সার্চিং এবং সর্টিং যেমন টপোলজিক্যাল সর্টে ডেপট ফার্স্ট সার্চ ব্যবহার করা হয়। কানেক্টেড কম্পোনেন্ট গুলো বের করার জন্যও ডেপথ ফার্স্ট সার্চ ব্যবহার করা যায়। আমরা সাধারনত যখন কোন ম্যাজ/ধাঁধা সমাধান করি, ডেপথ ফার্স্ট সার্চ এর মাধ্যমেই করি।

ডেপথ ফার্স্ট সার্চ অ্যালগরিদমের সুডোকোড নিচে দেওয়া হলো। সোর্সঃ উইকিপিডিয়া।

কমপ্লেক্সিটি: ডেপথ ফাস্ট সার্চ করার সময় আমরা প্রতিটি নড [V] একবার এবং প্রতিটা এজ [E] এ একবার গিয়েছি, তাই কমপ্লেক্সিটি হবে O(V+E)।

কমপ্লিটনেসঃ ডেপথ ফাস্ট সার্চ কমপ্লিট না। সার্চ করার সময় এটি একটি লুপে পড়তে পারে এবং তখন আর এটি সব গুলো নডে সার্চ করতে পারবে না।

মূল কনসেফট বুঝলে যে কোন ল্যাঙ্গুয়েজেই ইমপ্লিমেন্ট করা যাবে। আর ইমপ্লিমেন্ট করতে না পারলে গুগলে সার্চ করলেই অনেক কোড পাওয়া যাবে। তাই আর কোন কোড শেয়ার করলাম না।

রিলেটেড লেখাঃ

• গ্রাফ থিওরি, গ্রাফের রিপ্রেজেন্টেশন এবং ইমপ্লিমেন্টেশন
• ব্রেডথ ফার্স্ট সার্চ অ্যালগরিদম – Breadth-first search