ለግራፍ ጥልቅ የመጀመሪያ ፍለጋ (ዲ.ኤፍ.ኤስ)


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ GE የጤና ኢንፎሲስ MAQ o9 መፍትሄዎች UHG Optum
ጥልቀት የመጀመሪያ ፍለጋ ግራፍ

ጥልቀት የመጀመሪያ ፍለጋ በዛፍ / ግራፍ የውሂብ መዋቅር ውስጥ ማለፍ ወይም ፍለጋ ስልተ ቀመር ነው DFS ን ለማጣራት የምንጠቀምበት የኋላ መመለሻ ፅንሰ-ሀሳብ ፡፡ እሱ በተሰጠበት ጫፍ (በማንኛውም የዘፈቀደ ግጥም) ይጀምራል እና ይቃኘው እና አሁን ካለው ጫፍ ጋር የተገናኘውን ማንኛውንም ይጎብኙ እና እሱን ማሰስ ይጀምሩ። ምንም የተገናኙ አንጓዎች የሌለን አንድ ጫፍ እስክናገኝ ድረስ ይህንን እርምጃ ይድገሙ እና ከዚያ በኋላ መከታተያ እንጠቀማለን እና ቀደም ሲል የተጎበኘውን ጥቅል በአንድ ቁልል ውስጥ ይደምሩ ፡፡ ሁሉንም ጫፎች እስክንጎበኝ ድረስ የኋላ መመለሻ ፅንሰ-ሀሳብ ይጠቀሙ (ቁልል ባዶ አይደለም)።

ማስታወሻ: እኛ እንጠቀማለን ቁልል የተጎበኙትን ጫፎች በማከማቸት ከላይ ያለውን አመክንዮ ለመተግበር የመረጃ አደረጃጀት ይተይቡ ፡፡

የጥልቀት የመጀመሪያ ፍለጋ (DFS) ደረጃ በደረጃ ማብራሪያ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

 

ጥልቀት የመጀመሪያ ፍለጋ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

 

ጥልቀት የመጀመሪያ ፍለጋ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

ጥልቀት የመጀመሪያ ፍለጋ

 

 

 

 

 

 

 

ማስታወሻ:

  • ለተለየ ግራፍ ከአንድ በላይ ዲ.ኤፍ.ኤስ (እንደ ከላይ ግራፍ ያለ) ይቻላል ፡፡ ከላይ ለተጠቀሰው ግራፍ ልክ እንደሌሎች ሌሎች DFS (1,3,4,5,7,62) ፣ (1,2,3,4,7,5,6) are ናቸው ፡፡
  • በሁለትዮሽ ዛፍ ውስጥ Inorder ፣ Preorder እና Postorder transversal በ DFS መተላለፍ ስር ይመጣል ፡፡

የማስፈፀም  DFS

የጥልቀት የመጀመሪያ ፍለጋ C ++ ፕሮግራም

/*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)

ኦ (V + E) V ቁንጮዎች ቁጥር ሲሆን E ደግሞ የጠርዙ ቁጥር ነው ፡፡

ማጣቀሻ

ቃለ መጠይቅ ጥያቄዎች።