ডিএফএস রিকার্শন (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






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.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment