গ্রাফের জন্য ডেপথ ফার্স্ট সার্চ (DFS)

ডেপথ ফার্স্ট সার্চ (DFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমে একটি স্টার্টিং ভার্টেক্স দেওয়া থাকে, এবং যখন একটি অ্যাডজেসেন্ট ভার্টেক্স পাওয়া যায়, তবে সেটি প্রথমে ভিজিট করে এবং একইভাবে ট্রাভার্স করার চেষ্টা করে।

এটি যতটা গভীরে যেতে পারে চলে যায়, তারপর নতুন পাথ খুঁজে বের করার জন্য ব্যাকট্র্যাক করে পূর্বের ভার্টেক্সে ফিরে আসে।

ইটারেটিভভাবে DFS ইমপ্লিমেন্ট করতে, আমাদের স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হবে। যদি আমরা রিকার্সিভলি করতে চাই, তবে এক্সটার্নাল স্ট্যাক দরকার নয়, রিকার্শন কলের জন্য ইন্টারনাল স্ট্যাকে করা যায়।

ইনপুট: একটি গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স।

  A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0

আউটপুট: DFS ট্রাভার্সাল: C F E B D A

অ্যালগরিদম

dfs(vertices, start)

ইনপুট − সকল ভার্টেক্সের লিস্ট, এবং স্টার্ট নোড।

আউটপুট − গ্রাফের সকল নোড ট্রাভার্স করুন।

Begin
    initially make the state to unvisited for all nodes
    push start into the stack
    while stack is not empty, do
        pop element from stack and set to u
        display the node u
        if u is not visited, then
            mark u as visited
            for all nodes i connected to u, do
                if ith vertex is unvisited, then
                    push ith vertex into the stack
                    mark ith vertex as visited
                done
        done
End

উদাহরণ (C++)

#include 
#include 
using namespace std;
#define NODE 6
typedef struct node{
    int val;
    int state; //status
}node;
int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};
void dfs(node *vertex, node start){
    node u;
    stack myStack;
    for(int i = 0; i < NODE; i++){
        vertex[i].state = 0;//not visited
    }
    myStack.push(start);
    while(!myStack.empty()){
        u = myStack.top();
        myStack.pop();
        cout << char(u.val+'A') << " ";
        if(u.state != 1){
            u.state = 1;
            vertex[u.val].state = 1;
            for(int i = 0; i < NODE; i++){
                if(graph[i][u.val]){
                    if(vertex[i].state == 0){
                        myStack.push(vertex[i]);
                        vertex[i].state = 1;
                    }
                }
            }
        }
    }
}
int main(){
    node vertices[NODE];
    node start;
    char s;
    for(int i = 0; i < NODE; i++){
        vertices[i].val = i;
    }
    s = 'C';//starting vertex C
    start.val = s-'A';
    cout << "DFS Traversal: ";
    dfs(vertices, start);
    cout << endl;
}

আউটপুট

DFS Traversal: C F E B D A