ग्राफ के लिए डेप्थ फर्स्ट सर्च (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 1 0 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

उदाहरण

#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

आउटपुट
DFS Traversal: C F E B D A