মডিউল ৩_২ঃ DFS ইমপ্লিমেন্টশন

DFS ইমপ্লিমেন্টশন

আমরা এখন DFS ট্রাভারসাল এলগোরিদমটি স্টেপ বাই স্টেপ কোড এ দেখার চেষ্টা করব।

এখানে প্রথমে আমরা মেইন ফাংশনটি বোঝার চেষ্টা করব। প্রথমে আমরা নোড সংখ্যা ও এডজ সংখ্যা ইনপুট নিয়েছি। এরপর একটি লুপের মাধ্যমে কোন নোড দুইটির মধ্যে এডজ থাকবে সেটা অ্যাডজেসেন্সি লিস্ট এর মধ্যে নিয়ে নিচ্ছি।

int n, e;
cin >> n >> e;
while (e--)
{
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
}

এবার ভিজিটেড এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি false হিসেবে। সবশেষে DFS ফাংশনকে কল করছি source কে 0 ধরে।

memset(vis, false, sizeof(vis));
dfs(0);

dfs function এর মধ্যে parameter হিসেবে src (অর্থাৎ source) কে নেয়া হয়েছে। এরপর src কে প্রিন্ট করা হয়েছে এবং সেইটি src টিকে (অর্থাৎ সেই নোডটিকে) ভিজিটেড করা হয়েছে। এরপর src এর chlid গুলোকে লুপ ব্যবহার করে বের করা হয়েছে এবং লুপের ভিতরে কোন child আনভিজিটেড হলে সেইটি child নোডকে দিয়ে recurisve কল করা হয়েছে।

void dfs(int src)
{
    cout << src << endl;
    vis[src] = true;
    for (int child : v[src])
    {
        if (vis[child] == false)
            dfs(child);
    }
}

এই হয়ে গেল আমাদের DFS ট্রাভারসাল।

---

সম্পূর্ণ কোডটি DFS ইমপ্লিমেন্টশনের

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> v[N];
bool vis[N];

void dfs(int src)
{
    cout << src << endl;
    vis[src] = true;
    for (int child : v[src])
    {
        if (vis[child] == false)
            dfs(child);
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(vis, false, sizeof(vis));
    dfs(0);
    return 0;
}