ग्राफ के लिए डेप्थ फर्स्ट सर्च (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
    प्रारंभ में सभी नोड्स के लिए स्थिति को अनविजिटेड बनाएं
    प्रारंभ को स्टैक में पुश करें
    while स्टैक खाली नहीं है, do
        स्टैक से एलिमेंट पॉप करें और u पर सेट करें
        नोड u प्रदर्शित करें
        यदि u विजिटेड नहीं है, then
            u को विजिटेड के रूप में चिह्नित करें
            u से जुड़े सभी नोड्स i के लिए, do
                यदि iवां वर्टेक्स अनविजिटेड है, then
                    iवें वर्टेक्स को स्टैक में पुश करें
                    iवें वर्टेक्स को विजिटेड के रूप में चिह्नित करें
                done
        done
End

उदाहरण (C++)

#include 
#include 
using namespace std;
#define NODE 6
typedef struct node{
    int val;
    int state; //स्थिति
}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; //विजिट नहीं किया
    }
    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'; //प्रारंभिक वर्टेक्स C
    start.val = s-'A';
    cout << "DFS Traversal: ";
    dfs(vertices, start);
    cout << endl;
}

आउटपुट

DFS Traversal: C F E B D A