DFS(Depth First Search) Algorithm(Part-1)

Posted By 1 year ago

DFS বুঝতে হলে stack নামক data structure এর সম্বন্ধে আগে জানতে হবে।এটি একটি তাক এর মত।যেখানে ডাটা একটির উপর আরেকটি পরপর রাখা যায়। ঠিক যামন্টি বাসায় খাবার এর প্লেটগুলো রাখা হয়।খাবার প্লেটগুলো রাখার সময় এমনভাবে রাখা হয়,যাতে সবচেয়ে শেষে রাখা প্লেটটি সবার আগে হাতের কাছে পাওয়া যায়।এবং সবচেয়ে প্রথমে থাকা প্লেটটির সন্ধান মিলবে সবার শেষে। DFS দিয়ে গ্রাফটি Travarse করার সময়।একটি একটি করে নোডগুলোকে এভাবেই stack আকারে রাখা হবে।যাতে সবচেয়ে শেষে প্রবেশ করানো নোডটি হয় top of stack এবং সবার আগে এটিই হাতের কাছে পাওয়া যায়।

DFS Algorithm :

এখন দেখি এলগরিদমটি কিভাবে কাজ করে।
এখানেও বি এফ এস এর মত যথারীতি G প্রদত্ত graph টি ,V vertices বা nodeসংখ্যা,E edge সংখ্যা,pred নোডটির parent এবং color নোডটির রঙ নির্দেশ করে ।এবং white নির্দেশ করে নোডটি ভিজিট হয়নি, grey মানে বুঝায় নোডটি ভিজিট হয়েছে কিন্তু সব চাইল্ড ভিজিট হয়নি আর black বুঝায় যে সব চাইল্ড ভিজিট করা হয়ে গেছে।

ছবিটির গ্রাফটিতে ধরি 1 আমাদের source node অর্থাৎ 1 node থেকেই আমাদের যাত্রা শুরু হবে।
এ পর্যায়ে 1 node এর রঙ হয়ে যাবে grey।কারণ এ নোডটি ভিজিট করা হয়েছে।
1 এর ২ টি child node রয়েছে 2 এবং 3 .যেকোন একটি নোড প্রথমে ভিজিট করবে।ধরা যাক এক্ষেত্রে 2 node টি প্রথমে ভিজিট করা হল।তাহলে প্রথমে এর সকল child node ভিজিটেড হবে,তারপরই এবং child node দেরও child node ভিজিট হবে।তারপর 1 node এর কাছে ফেরত আসবে। অর্থাৎ সবচেয়ে শেষে ভিজিট করা নোড এর সব চাইল্ড নোড গুলো ভিজিট হলেই এর আগের নোড বা parent এর কাছে ফিরে আসবে।প্রথমে 2 node এর child 4 কে ভিজিট করবে।যেহেতু এর কোন child নেই তাই 4 এর রঙ হয়ে যাবে কালো এবং ঙ্গামরা 2 এর কাছে ফেরত যাবো।তারপর 2 থেকে এর child 5 ভিজিট হবে।এবং এরও কোন child না থাকায় আবার 2 তে ফেরত যাবে।এবং 2 এর রঙ হয়ে যাবে কালো।যেহেতু 2 এর সকল নোড ভিজিটেড হয়ে গেছে তাই এখন আমরা 1 এর কাছে ফেরত যাবো।এরপর 1 এর অপর child node 3 এর কাছে যাবে।এবং 3 এর কোন child node না থাকায় এর রঙ কালো হয়ে যাবে এবং আমরা 1 এর কাছে ফেরত যাবো।এ পর্যায়ে 1 এর রঙ কালো হয়ে যাবে।
এভাবে আমাদের গ্রাফ ভিজিট করা সম্পন্ন হবে।