DFS (Depth-First Search)

গ্রাফে ট্রাভার্সিং এর অপর একটি জনপ্রিয় এলগোরিদম ডিএফএস । ডিএফএস জানার আগে বিএফএস এর টিউটোরিয়ালটি দেখে এসো - BFS Tutorial Link
বিএফএস এলগোরিদমের সাথে ডিএফএস এর অনেক সাদৃশ্য আছে। বিএফএস এ আমরা শর্টেস্ট পাথ বের করতাম। ডিএফএস এ আমরা যেকোন একটি নোড থেকে যেসব নোডে ট্রাভার্স করা যায় তা বের  করব। ডিএফএস ইমপ্লিমেন্ট করা হয় স্ট্যাক ব্যবহার করে। আমরা জানি যে স্ট্যাক লাস্ট ইন ফার্স্ট আউট মেথডলজিতে এক্সেকিউশন করে। আমরা ডিএফএস এর জন্য রিকার্শন ব্যবহার করে স্ট্যাক এর ডাটা স্ট্রাকচার ইমপ্লিমেন্ট করব। ডিএফএস এর এলগোরিদমটি  এমন -

• সব নোড গুলো প্রথমে Ready স্টেট এ থাকবে (সাদা রং দিয়ে চিহ্নিত) 
• Starting Node কে স্ট্যাকে পুশ করি এবং নোডটির Status Waiting State এ পরিবর্তন করি
• যতক্ষণ স্ট্যাক খালি না হয়, পরবর্তী দুইটি ধাপের জন্য লুপ চালাই

1. স্ট্যাক এর টপ এর ডাটা পপ করি বা রিমুভ করি এবং নোডটির রং পরিবর্তন করে গ্রে করি   
2. পপকৃত নোডটির Neighbor নোড গুলো কে স্ট্যাকে পুশ করি  এবং নোডটির Status Waiting State এ পরিবর্তন করি (নীল রং দ্বারা নির্দেশিত)

উপরের গ্রাফটি লক্ষ্য কর।এখন মনেকর, আমি নোড 1 থেকে যেসব নোডে যাওয়া যায় তা বের করব। যে নোড নিয়ে প্রথমে ট্রাভার্স শুরু করব, সেটি লাল রং দিয়ে চিহ্নিত করি, এবং সেই নোডের Neighbor নোডগুলোকে নীল রং দিয়ে চিহ্নিত করি। যেসব নোড ভিজিটেড হয়ে যাবে সেইগুলো গ্রে রং দিয়ে চিহ্নিত করি।

প্রথমে নোড 1 কে স্ট্যাকে পুশ করি। যেহেতু নোড 1 স্ট্যাকে টপে আছে সেহেতু নোড 1 কে স্ট্যাক থেকে পপ করি, নোড 1 কে  গ্রে রং দিয়ে চিহ্নিত করি এবং নোড 1 এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1।

এখন স্ট্যাকে টপে 2 আছে। 2 কে পপ করি এবং এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1, 2

এখন স্ট্যাকে টপে 4 আছে। 4 কে পপ করি এবং এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1, 2, 4

এখন স্ট্যাকে টপে 9 আছে। 9 কে পপ করি এবং নোড 9 এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। ভিজিটেড নোড সমূহ- 1, 2, 4, 9

এখন স্ট্যাকে টপে 5 আছে। 5 কে পপ করি এবং নোড 5 এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। ভিজিটেড নোড সমূহ- 1, 2, 4, 9, 5

এখন স্ট্যাকে টপে 3 আছে। 3 কে পপ করি এবং এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1, 2, 4, 9, 5, 3

এখন স্ট্যাকে টপে 6 আছে। 6 কে পপ করি এবং এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1, 2, 4, 9, 5, 3, 6

এখন স্ট্যাকে টপে 12 আছে। 12 কে পপ করি এবং নোড 12 এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। ভিজিটেড নোড সমূহ-1, 2, 4, 9, 5, 3, 6, 12 । একইভাবে নোড 7 এর এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। নোড 7 কে ভিজিট করার পর ভিজিটেড নোড সমূহ-1, 2, 4, 9, 5, 3, 6, 12, 7

এখন স্ট্যাকে টপে 8 আছে। 8 কে পপ করি এবং এর Neighbor নোডগুলোকে স্ট্যাকে পুশ করি। Neighbor নোডগুলোকে  নীল রং দিয়ে চিহ্নিত করি। ভিজিটেড নোড সমূহ- 1, 2, 4, 9, 5, 3, 6, 12, 7, 8

এখন স্ট্যাকে টপে 10 আছে। 10 কে পপ করি এবং এবং নোড 10 এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। ভিজিটেড নোড সমূহ- 1, 2, 4, 9, 5, 3, 6, 12, 7, 8, 10 । একইভাবে নোড 11 এর এর Neighbor নোড না থাকায় স্ট্যাকে কিছু পুশ করবো না। নোড 11 কে ভিজিট করার পর ভিজিটেড নোড সমূহ-1, 2, 4, 9, 5, 3, 6, 12, 7, 8, 10, 11

নোড 11 কে ভিজিট করার পর, স্ট্যাক সম্পূর্ণ খালি হয়ে গেছে। ভিজিটেড নোড গুলোই হচ্ছে স্টার্টিং নোড 1 থেকে Reachable । তোমরা একটি ব্যাপার কি লক্ষ্য করেছ ??? ডিএফএস এলগোরিদমের সাথে বাইনারি ট্রি এর In Order Traversal এর অনেক সাদৃশ্য আছে। 

Code:

/* DFS */

#include<bits/stdc++.h>
using namespace std;
vector <int> G[100];
bool visit[100]={0};

void dfs(int u)
{
    printf("%d ", u);
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(visit[v]==0)
        {
            visit[v]=1;
            dfs(v);
        }
    }
}


int main()
{
    int n, m, u, v, u1, v1;
    scanf("%d%d", &n, &m);  //n is number of node & m is number of edge
    for(int i=0; i<m; i++)
    {
        scanf("%d%d", &u, &v);  //u and v are two two node of an edge
        G[u].push_back(v);
        G[v].push_back(u); // For bidirectional edge
    }
    visit[1]=1;
    dfs(1);
    return 0;
}

/*
Input:
12 11
1 2
1 3
2 4
2 5
3 6
3 7
3 8
4 9
6 12
8 10
8 11
*/