Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

ग्राफ़ के लिए डेप्थ फर्स्ट सर्च या डीएफएस

<घंटा/>

डेप्थ फर्स्ट सर्च (डीएफएस) एक ग्राफ ट्रैवर्सल एल्गोरिथम है। इस एल्गोरिथम में एक प्रारंभिक शीर्ष दिया जाता है, और जब एक आसन्न शीर्ष मिलता है, तो यह पहले उस आसन्न शीर्ष पर जाता है और उसी तरह से पार करने का प्रयास करता है।

ग्राफ़ के लिए डेप्थ फर्स्ट सर्च या डीएफएस

यह पूरी गहराई के माध्यम से चलता है, जितना भी जा सकता है, उसके बाद यह नया पथ खोजने के लिए पिछले शिखर तक पहुंचने के लिए पीछे हट जाता है।

डीएफएस को पुनरावृत्त तरीके से लागू करने के लिए, हमें स्टैक डेटा संरचना का उपयोग करने की आवश्यकता है। यदि हम इसे पुनरावर्ती रूप से करना चाहते हैं, तो बाहरी स्टैक की आवश्यकता नहीं है, इसे रिकर्सन कॉल के लिए आंतरिक स्टैक किया जा सकता है।

इनपुट :ग्राफ का एडजेंसी मैट्रिक्स।

  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(शीर्ष, प्रारंभ)

इनपुट - सभी शीर्षों की सूची, और प्रारंभ नोड।

आउटपुट - ग्राफ़ में सभी नोड्स को ट्रैवर्स करें।

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

उदाहरण

#include<iostream>
#include<stack>
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<node> myStack;
   for(int i = 0; i<NODE; i++){
      vertex[i].state = 0;//not visited
      }
   myStack.push(start);
      while(!myStack.empty()){
         //pop and print node
         u = myStack.top();
         myStack.pop();
         cout << char(u.val+'A') << " ";
         if(u.state != 1){
            //update vertex status to visited
            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

  1. ग्राफ़ के लिए चौड़ाई पहली खोज या बीएफएस

    चौड़ाई पहली खोज (बीएफएस) ट्रैवर्सल एक एल्गोरिथम है, जिसका उपयोग किसी दिए गए ग्राफ़ के सभी नोड्स पर जाने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिथम में एक नोड का चयन किया जाता है और फिर सभी आसन्न नोड्स को एक-एक करके देखा जाता है। आसन्न सभी शीर्षों को पूरा करने के बाद, यह एक और शीर्षों की जाँच करने क

  1. डेटा संरचना में एक डिग्राफ पर गहराई-पहली खोज

    ग्राफ की पहली गहराई खोज समान होती है। लेकिन डिग्राफ या निर्देशित ग्राफ के लिए, हम कुछ प्रकार के किनारों को पा सकते हैं। DFS एल्गोरिथम एक ट्री बनाता है जिसे DFS ट्री कहा जाता है। किनारों के चार प्रकार होते हैं जिन्हें - . कहा जाता है ट्री एज (T) − वे किनारे जो DFS ट्री में मौजूद होते हैं फॉरवर्

  1. Facebook ग्राफ़ खोज के लिए अपना खाता गोपनीयता तैयार करें [साप्ताहिक Facebook युक्तियाँ]

    हर बार जब फेसबुक हमारे दोस्तों के बारे में अधिक जानने के लिए एक नई सुविधा जारी करता है, तो बहुत से लोग महसूस करते हैं कि उनकी गोपनीयता सेटिंग्स अब पर्याप्त नहीं हैं। उनकी नवीनतम नई सुविधा, Facebook ग्राफ़ खोज, कोई अपवाद नहीं है - बहुत से लोग इस बात को लेकर थोड़ा चिंतित हैं कि किस प्रकार की चीज़ें मि