एक ग्राफ के लिए पहली खोज (डीएफएस) गहराई


कठिनाई स्तर आसान
में अक्सर पूछा जीई हेल्थकेयर इंफोसिस MAQ ओ 9 के समाधान यूएचजी ऑप्टम
गहराई पहली खोज ग्राफ

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

नोट: हम उपयोग ढेर टाइप किए गए डेटा को संरचना में ऊपर के लॉरिज़ को लागू करने के लिए विज़िट किए गए कोने को संग्रहीत करके।

डेप्थ फर्स्ट सर्च (डीएफएस) के स्टेप बाई स्टेप स्पष्टीकरण

 

गहराई पहली खोज

 

 

गहराई पहली खोज

 

गहराई पहली खोज

 

गहराई पहली खोज

 

गहराई पहली खोज

 

 

गहराई पहली खोज

 

गहराई पहली खोज

 

गहराई पहली खोज

 

 

 

 

 

 

 

नोट:

  • किसी विशेष ग्राफ के लिए (उपरोक्त ग्राफ की तरह) एक से अधिक डीएफएस संभव है। उपरोक्त ग्राफ के लिए कुछ अन्य संभावित डीएफएस की तरह (1,3,4,5,7,62), (1,2,3,4,7,5,6)… हैं।
  • द्विआधारी पेड़ में, Inorder, Preorder और Postorder traversal DFS traversal के अंतर्गत आता है।

का कार्यान्वयन  डीएफएस

गहराई के लिए सी ++ प्रोग्राम पहली खोज

/*C++ Implementation of the DFS for a given graph using STL.*/
#include <bits/stdc++.h>
using namespace std;
int main() {
  int nodes,edges;
  /*take input*/
  cin>>nodes>>edges;
  vector<int> v[nodes+1];
  bool visited [nodes+1];
  /*initalise all vertices as false(unvisited)*/
  memset(visited,false,sizeof(visited));
  /*make graph using vector*/
  for(int i=0;i<edges;i++)
  {
      int x,y;
      cin>>x>>y;
      /*add edge between x and y*/
      v[x].push_back(y);
      /*add edge between y and x*/
      v[y].push_back(x);
  }
  int start;
  /*Take input node at which the DFS starts*/
  cin>>start;
  stack<int> s;
  /*Push the vertex at which the DFS start*/
  s.push(start);
  /*vector use to store the answer*/
  vector<int> dfs;
  /*perform the operation till the size of stack is not empty*/
  while(!s.empty())
  {
      int top=s.top();
      s.pop();
      /*if the vertex is not visited then add it to dfs*/
      if(visited[top]==false)
      {
          visited[top]=true;
           dfs.push_back(top);
      }
      /*explore the current vertex*/
      for(int  i=0;i<v[top].size();i++)
      {
          if(visited[v[top][i]]==false)
          {
              s.push(v[top][i]);
          }
      }
  }
  /*print the DFS for given graph at starting with given node*/
  for(int i=0;i<nodes;i++)
  {
      cout<<dfs[i]<<" ";
  }
  cout<<"\n";
  return 0;
}
Input:
7 9
1 2
1 3
2 3
3 4
4 5
4 6
4 7
5 7
6 7
1
Output: 
1 3 4 7 6 5 2

की समय जटिलता गहराई पहली खोज (DFS)

O (V + E) जहां V, कोने की संख्या है और E किनारों की संख्या है।

संदर्भ

साक्षात्कार के प्रश्न