মডিউল ৩_১ঃ DFS
DFS এর পূর্ণরূপ হল Depth-First Search। এইটি গ্রাফের গভীরে গিয়ে নোড ট্রাভাস এবং সার্চ করতে পারে।
নিচে DFS কিভাবে কাজ করতে সেইটি বিস্তারিত লিখা হলঃ
গ্রাফের ইনপুট
6 7 0 3 0 1 0 2 1 5 2 5 2 4 3 4
এইখানে গ্রাফের প্রথমে ইনপুট নেয়া N ( Number of nodes ) এবং E ( Number of edges ) উপরের ইনপুটে N=6 এবং E=7 , এই এরপরই E বার ইনপুট নিয়া হয়েছে কোন নোড কোন নোডের সাথে connection আছে।
নিচে ইনপুটটির edge গুলো অনুসারে গ্রাফটি আঁকা হল ।
এই গ্রাফের ইনপুটকে অ্যাডজাসেন্সি লিস্ট এর মধ্যে রাখতে array of vector টি এইরকম হবে।
বুঝার সুবিধাতে এইভাবে আঁকা হল। কোন নোডের সাথে কোন কোন নোড connected আছে।
আমাদের dfs নামের একটি function বানানো থাকবে। dfs শুরু করার জন্য আমরা প্রথমে source পাঁঠিয়ে dfs কে কল করবো। ধরি উরের গ্রাফের source = 0 ।
-> এখন source = 0 দিয়ে dfs(0) কল করাইপ্রথমেই আমরা সেই 0 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 0 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 0 নোডের সাথে connected নোডগুলো হলঃ 1, 2, 3। তাহলে dfs(1) দিয়ে আবার function টি কল করবো।
-> এখন source = 1 দিয়ে dfs(1) কল করাই প্রথমেই আমরা সেই 1 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 -> 1 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 1 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 1 নোডের সাথে connected নোডগুলো হল 0, 5। এখানে 0 নোড ইতিমধ্যে ভিজিটেড তাই সেইটি আর ভিজিট করা যাবে না। তাহলে dfs(5) দিয়ে আবার function টি কল করবো ।
-> এখন source = 5 দিয়ে dfs(5) কল করাই প্রথমেই আমরা সেই 5 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 -> 1 -> 5 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 5 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 5 নোডের সাথে connected নোডগুলো হলঃ 1, 2। এখানে 1 নোড ইতিমধ্যে ভিজিটেড তাই সেইটি আর ভিজিট করা যাবে না। তাহলে dfs(2) দিয়ে আবার function টি কল করবো ।
-> এখন source = 2 দিয়ে dfs(2) কল করাই প্রথমেই আমরা সেই 2 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 -> 1 -> 5 -> 2 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 2 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 2 নোডের সাথে connected নোডগুলো হলঃ 0, 5, 4। এখানে 0 এবং 1 নোডগুলো ইতিমধ্যে ভিজিটেড তাই সেইগুলোতে আর ভিজিট করা যাবে না। তাহলে dfs(4) দিয়ে আবার function টি কল করবো ।
-> এখন source = 4 দিয়ে dfs(4) কল করাই প্রথমেই আমরা সেই 4 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 -> 1 -> 5 -> 2 -> 4 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 4 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 4 নোডের সাথে connected নোডগুলো হলঃ 2,3। এখানে 2 নোড ইতিমধ্যে ভিজিটেড তাই সেইটি আর ভিজিট করা যাবে না। তাহলে dfs(3) দিয়ে আবার function টি কল করবো ।
-> এখন source = 3 দিয়ে dfs(3) কল করাই প্রথমেই আমরা সেই 3 নোডকে ভিজিট করে ফেলবো। আমরা এখন পর্যন্ত ভিজিট করছেঃ 0 -> 1 -> 5 -> 2 -> 4 -> 3 নিচের চিত্রে ভিজিট করা নোড বুঝা জন্য ভিজিটেড নোডগুলোর কালার সবুজ করে দেয়া হলঃ
এরপর 3 নোডের সাথে connected গুলোর আনভিজিটেড একটি নোডে যাবো । 3 নোডের সাথে connected নোডগুলো হলঃ 0, 4। এএখানে 0 এবং 4 নোডগুলো ইতিমধ্যে ভিজিটেড তাই সেইগুলোতে আর ভিজিট করা যাবে না। তাহলে আর dfs function টি কল করবো নাহ।
এইভাবে DFS ট্রাভাসালের মাধ্যমে সব নোডগুলোকে ভিজিট করেছি।
Last updated