DFS Algorithm in Bangla (ডিএফএস রিকার্শন (DFS Recursion) )

ডিএফএস (Depth First Search) হল গ্রাফ ট্রাভার্স করার এক ধরনের পদ্ধতি । নাম শুনেই বুজতে পারছি যে এক্ষেত্রে গ্রাফ এর গভীর এ গিয়ে আগে নোড সার্চ করে। নিচের গ্রাফ এর চিত্র দেখে আমরা ডিএফএস চালায় গ্রাফ এর সব নোড ভিজিট করব ।

 

                                                                                                                                            

ডিএফএস রিকার্সন চালানোর জন্য আমরা একটি লিস্ট তৈরী করে নিব। এই লিস্ট এ থাকবে কোন নোড থেকে কোন কোন নোড এ যাওয়া যায় । তারপর এই লিস্ট এর মাধ্যমেই রিকার্শন চালিয়ে সব নোড ভিজিট করব ।

প্রথমে এডজ্যাসেন্ট লিস্ট এ চিত্রের মত করেই এলিমেন্ট পুশ করে রাখব । এখন dfs(1) রিকার্শন ফাংশন কল করলে প্রথমে 1 নম্বর নোড এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1

1 নম্বর নোড থেকে 2 এবং 3 নম্বর নোড এ যাওয়া যায় । প্রথমে 2 পুশ করার কারনে dfs(2) কল হবে এবং 2 এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2

এরপর 2 নম্বর নোড থেকে 1 4 এবং 5 নম্বর নোড এ যাওয়া যায়। যেহেতু 1 নম্বর নোড আগেই ভিজিট হয়েছে তাই 4 নম্বর নোড এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4

এরপর 4 নম্বর নোড থেকে 2 এবং 8 নম্বর নোড এ যাওয়া যায়। যেহেতু 2 নম্বর নোড আগেই ভিজিট হয়েছে তাই 8 নম্বর নোড এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4 8

এবার 8 নম্বর নোড থেকে 4 5 6 এবং 7 নম্বর নোড এ যাওয়া যায় । 4 নম্বর নোড আগেই ভিজিটেড তাই 5 নম্বর নোড এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4 8 5

এখন 5 নম্বর নোড থেকে 2 8 এ যাওয়া যায় কিন্তু এরা আগেই ভিজিটেড তাই রিকার্শন তার আগের স্টে্ট 8 এ ফিরে আসবে এবং 5 এর পরের এলিমেন্ট দেখবে ভিজিটেড কিনা । যেহেতু 6 আনভিজিটেড তাই 6 এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4 8 5 6

এখন 6 নম্বর নোড থেকে 3, 8 এ যাওয়া যায় । তাই 3 এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4 8 5 6 3

এরপর 3 নম্বর নোড থেকে 1 ,6 , 7  এ যাওয়া যায় । শুধুমাত্র 7 এই ভিজিট হয় নাই তাই 7 এ যাবে ।

ভিজিট সিকুয়েন্স ঃ  1 2 4 8 5 6 3 7

7 নম্বর নোড এ গিয়ে দেখবে যে  3 , 8 এ যাওয়া যায়। কিন্তু এরা তো ভিজিটেড । তারপর রিকার্শন এর স্টেট পপ হয়ে  আগের স্টেট যথাক্রমে 3 6 5 8 4 2 1 এ যাবে এবং সবগুলোর নোড এ ভিজিটেড পাবে । 1 এর পর রিকার্শনের আর কোন স্টেট থাকবে না অর্থাৎ স্ট্যাক খালি হয়ে যাবে এবং রিকার্শন থেমে প্রোগ্রাম শেষ হবে ।

কোড করাও সহজ । ভেক্টর এর এডজ্যাসেন্ট লিস্ট এ ইনপুট নিয়ে রিকার্শন চালালেই কাজ শেষ ।

#include <bits/stdc++.h>

using namespace std;

vector<long long int>edges[100];

vector<long long int>result;

long long int visited[1000],c=0;

long long int dfs(long long int s)

{

    long long int x,y,z;

    if(visited[s]==0)

    {

        visited[s]=1;

        for(x=0;x<edges[s].size();x++)

        {

            z=edges[s][x];

            if(visited[z]==0)

            {

                result.push_back(z);

                dfs(z);

            }

        }

    }

}

int main()

{

    long long int i,j,k,l,u,v,n,e;

    cin>>n>>e;

    for(i=1;i<=e;i++)

    {

        cin>>u>>v;

        if(i==1)

        {

            l=u;

        }

        edges[u].push_back(v);

        edges[v].push_back(u);

    }

    memset(visited,0, sizeof visited);

    result.push_back(l);

    dfs(l) ;

    cout<<"\nVisit Sequence= ";

    for(k=0;k<result.size();k++)

    {

        cout<<result[k]<<" ";

    }

    return 0;

}

Related Problems : UVA 459 Graph Connectivity

                               SPOJ GraCon Connectivity

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here