> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/module_3/_-dfs-1.md).

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

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

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

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

```cpp
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 ধরে।

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

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

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

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

***

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

```cpp
#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;
}
```