depth first search c program traverse graph
यह ट्यूटोरियल C ++ में गहराई से पहली खोज (DFS) को शामिल करता है जिसमें A ग्राफ़ या ट्री ट्रैवर्सेड डेप्थवाइज़ है। आप DFS एल्गोरिथम और कार्यान्वयन भी सीखेंगे:
गहराई-पहली खोज (डीएफएस) अभी तक एक पेड़ या ग्राफ को पार करने के लिए उपयोग की जाने वाली एक और तकनीक है।
डीएफएस एक रूट नोड या एक स्टार्ट नोड के साथ शुरू होता है और फिर ग्राफ या एक पेड़ में गहराई तक जाकर वर्तमान नोड के आसन्न नोड्स की पड़ताल करता है। इसका मतलब यह है कि डीएफएस में नोड्स का सामना तब तक किया जाता है जब तक कि कोई बच्चों का सामना नहीं करना पड़ता।
एक बार पत्ती नोड तक पहुंचने के बाद, डीएफएस पीछे हट जाता है और इसी तरह से कुछ और नोड्स की खोज शुरू करता है।
=> यहां शुरुआती सी ++ प्रशिक्षण गाइड देखें।
आप क्या सीखेंगे:
सी ++ में पहली खोज (डीएफएस) की गहराई
BFS के विपरीत, जिसमें हम नोड्स चौड़ाई का पता लगाते हैं, DFS में हम नोड्स की गहराई से खोज करते हैं। डीएफएस में हम पता लगाया जा रहा नोड्स के भंडारण के लिए एक स्टैक डेटा संरचना का उपयोग करते हैं। वे किनारे जो हमें अस्पष्टीकृत नोड्स की ओर ले जाते हैं, उन्हें 'डिस्कवरी एज' कहा जाता है, जबकि पहले से विज़िट किए गए नोड्स के किनारों को 'ब्लॉक एज' कहा जाता है।
अगला, हम डीएफएस तकनीक के लिए एल्गोरिथ्म और छद्म कोड देखेंगे।
DFS एल्गोरिथम
- चरण 1: स्टैक में रूट नोड या स्टार्टिंग नोड ऑफ ट्री या ग्राफ डालें।
- चरण 2: स्टैक से शीर्ष आइटम को पॉप करें और इसे विज़िट की गई सूची में जोड़ें।
- चरण 3: चिह्नित नोड के सभी आसन्न नोड्स का पता लगाएं और उन लोगों को जोड़ें जो अभी तक नहीं आए हैं, स्टैक पर।
- चरण 4 : स्टेप 2 और 3 को तब तक दोहराएं जब तक स्टैक खाली न हो जाए।
स्यूडोकोड
DFS के लिए छद्म कोड नीचे दिया गया है।
उपरोक्त छद्म कोड से, हम देखते हैं कि DFS एल्गोरिदम को प्रत्येक शीर्ष पर पुनरावर्ती कहा जाता है ताकि यह सुनिश्चित किया जा सके कि सभी कोने का दौरा किया गया है।
दृष्टांत के साथ ट्रावेल्स
आइए अब हम ग्राफ़ के डीएफएस ट्रैवर्सल का वर्णन करते हैं। स्पष्टता के उद्देश्यों के लिए, हम उसी ग्राफ का उपयोग करेंगे जिसका उपयोग हमने बीएफएस चित्रण में किया था।
मान लें कि शुरुआती नोड या स्रोत नोड है। सबसे पहले, हम इसे विज़िट के रूप में चिह्नित करते हैं और इसे विज़िट की गई सूची में जोड़ते हैं। फिर हम स्टैक में इसके सभी आसन्न नोड्स को धक्का देते हैं।
अगला, हम प्रक्रिया करने के लिए आसन्न नोड्स में से एक लेते हैं यानी स्टैक के शीर्ष पर जो कि 1. हम इसे चिह्नित सूची में जोड़कर विज़िट के रूप में चिह्नित करते हैं। अब आसन्न नोड्स के लिए देखें 1. जैसा कि 0 पहले से ही देखी गई सूची में है, हम इसे अनदेखा करते हैं और हम 2 पर जाते हैं जो स्टैक के शीर्ष पर है।
अगला, हम नोड 2 का दौरा करते हैं। इसके आसन्न नोड 4 को स्टैक में जोड़ा जाता है।
इसके बाद, हम 4 को चिह्नित करते हैं जो स्टैक के शीर्ष पर जाता है। नोड 4 में केवल नोड 2 है जैसा कि पहले से ही दौरा किया गया है, इसलिए हम इसे अनदेखा करते हैं।
इस स्तर पर, केवल नोड 3 स्टैक में मौजूद है। इसका आसन्न नोड 0 पहले से ही देखा गया है, इसलिए हम इसे अनदेखा करते हैं। अब हम 3 का दौरा करते हैं।
अब स्टैक खाली है और विज़िट की गई सूची दिए गए ग्राफ की गहराई-पहले ट्रैवर्सल के अनुक्रम को दिखाती है।
यदि हम दिए गए ग्राफ और ट्रैवर्सल अनुक्रम का निरीक्षण करते हैं, तो हम ध्यान देते हैं कि डीएफएस एल्गोरिथ्म के लिए, हम वास्तव में ग्राफ गहराई-वार को पार करते हैं और फिर नए नोड्स का पता लगाने के लिए इसे फिर से पीछे करते हैं।
गहराई-पहली खोज कार्यान्वयन
C ++ का उपयोग करके DFS ट्रैवर्सल तकनीक को लागू करें।
#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'< आउटपुट:
दिए गए ग्राफ़ के लिए पहला-पहला ट्रैवर्सल:
0 1 2 4 3
हमने एक बार फिर ग्राफ का उपयोग उस कार्यक्रम में किया है जिसका उपयोग हम चित्रण प्रयोजनों के लिए करते हैं। हम देखते हैं कि डीएफएस एल्गोरिथ्म (दो कार्यों में विभाजित) को ग्राफ में प्रत्येक शीर्ष पर पुनरावर्ती कहा जाता है ताकि यह सुनिश्चित किया जा सके कि सभी कोने का दौरा किया जाता है।
रनटाइम विश्लेषण
DFS की समय जटिलता BFS के समान है O (| V | + | E |) जहाँ V, कोने की संख्या है और E किसी दिए गए ग्राफ़ में किनारों की संख्या है।
बीएफएस के समान, इस बात पर निर्भर करता है कि ग्राफ मुश्किल से भरा है या घनी आबादी है, समय की जटिलता की गणना में प्रमुख कारक क्रमशः कोने या किनारे होंगे।
Iterative DFS
डीएफएस तकनीक के लिए ऊपर दिखाया गया कार्यान्वयन प्रकृति में पुनरावर्ती है और यह फ़ंक्शन कॉल स्टैक का उपयोग करता है। हमारे पास डीएफएस लागू करने के लिए एक और भिन्नता है यानी “ Iterative गहराई-पहली खोज ”। इसमें, हम विज़िट किए गए शीर्षों को पकड़ने के लिए स्पष्ट स्टैक का उपयोग करते हैं।
हमने पुनरावृत्त डीएफएस के लिए कार्यान्वयन नीचे दिखाया है। ध्यान दें कि कार्यान्वयन BFS के समान है सिवाय उस कारक के जो हम एक कतार के बजाय स्टैक डेटा संरचना का उपयोग करते हैं।
#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal:
'; gidfs.DFS(); return 0; } आउटपुट:
Iterative गहराई-प्रथम ट्रैवर्सल का आउटपुट:
0 3 2 4 1
हम उसी ग्राफ का उपयोग करते हैं जो हमने अपने पुनरावर्ती कार्यान्वयन में उपयोग किया था। आउटपुट में अंतर इसलिए है क्योंकि हम पुनरावृत्ति कार्यान्वयन में स्टैक का उपयोग करते हैं। जैसा कि ढेर LIFO आदेश का पालन करते हैं, हमें डीएफएस का एक अलग क्रम मिलता है। उसी क्रम को प्राप्त करने के लिए, हम उल्टे क्रम में कोने सम्मिलित करना चाह सकते हैं।
BFS बनाम DFS
अब तक हमने रेखांकन यानी BFS और DFS दोनों के लिए ट्रावेलर तकनीकों पर चर्चा की है।
अब हम दोनों के बीच के अंतर को देखते हैं।
बीएफ डीएफएस 'चौड़ाई-पहली खोज' के लिए खड़ा है 'गहराई-पहली खोज' के लिए खड़ा है नोड्स को स्तर के आधार पर चौड़ाई का पता लगाया जाता है। नोड्स की गहराई-वार तब तक खोज की जाती है जब तक कि केवल पत्ती के नोड्स नहीं होते हैं और फिर अन्य अनवीकृत नोड्स का पता लगाने के लिए पीछे हट जाते हैं। बीएफएस कतार डेटा संरचना की मदद से किया जाता है। DFS को स्टैक डेटा संरचना की सहायता से किया जाता है। प्रदर्शन में धीमी। बीएफएस की तुलना में तेज़। दो नोड्स के बीच सबसे छोटा रास्ता खोजने में उपयोगी। ज्यादातर ग्राफ में चक्रों का पता लगाने के लिए उपयोग किया जाता है।
डीएफएस के आवेदन
- ग्राफ़ में चक्रों का पता लगाना: यदि हम ग्राफ़ में डीएफएस करते समय एक बैक एज पाते हैं तो हम निष्कर्ष निकाल सकते हैं कि ग्राफ में एक चक्र है। इसलिए एक ग्राफ में चक्रों का पता लगाने के लिए डीएफएस का उपयोग किया जाता है।
- रास्ता पाना: दो कोने x और y को देखते हुए, हम DFS का उपयोग करके x और y के बीच का रास्ता खोज सकते हैं। हम वर्टेक्स x से शुरू करते हैं और फिर स्टैक के रास्ते पर सभी वर्टिकल को धक्का देते हैं जब तक कि हम y से मुठभेड़ न करें। स्टैक की सामग्री एक्स और वाई के बीच का रास्ता देती है।
- न्यूनतम स्पानिंग ट्री और सबसे छोटा पथ: बिना भारित ग्राफ के डीएफएस ट्रैवर्सल हमें नोड्स के बीच न्यूनतम फैले हुए पेड़ और सबसे छोटा रास्ता देता है।
- सामयिक छँटाई: जब हम नौकरियों के बीच निर्भरता से नौकरियों को शेड्यूल करने की आवश्यकता होती है तो हम टोपोलॉजिकल सॉर्टिंग का उपयोग करते हैं। कंप्यूटर विज्ञान के क्षेत्र में, हम इसका उपयोग ज्यादातर लिंकर्स, डेटा क्रमांकन, निर्देश निर्धारण आदि में प्रतीक निर्भरता के समाधान के लिए करते हैं। डीएफएस का उपयोग टोपोलॉजिकल सॉर्टिंग में व्यापक रूप से किया जाता है।
निष्कर्ष
ट्यूटोरियल के अंतिम जोड़े में, हमने ग्राफ़ के लिए दो ट्रैवर्सल तकनीकों यानी बीएफएस और डीएफएस के बारे में और खोज की। हमने अंतरों के साथ-साथ दोनों तकनीकों के अनुप्रयोगों को भी देखा है। बीएफएस और डीएफएस मूल रूप से एक ग्राफ के सभी नोड्स पर जाने का एक ही परिणाम प्राप्त करते हैं लेकिन वे आउटपुट के क्रम में भिन्न होते हैं और जिस तरह से यह किया जाता है।
हमने दोनों तकनीकों के कार्यान्वयन को भी देखा है। जबकि बीएफएस एक कतार का उपयोग करता है, डीएफएस तकनीक को लागू करने के लिए ढेर का उपयोग करता है। इसके साथ, हम ग्राफ़ के लिए ट्रैवर्सल तकनीकों पर ट्यूटोरियल को समाप्त करते हैं। हम पेड़ों पर BFS और DFS का भी उपयोग कर सकते हैं।
विंडोज़ 10 मुफ्त डाउनलोड के लिए डीवीडी आरा
हम अपने आगामी ट्यूटोरियल में एक ग्राफ के नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए पेड़ों और फैले एल्गोरिदम के एक जोड़े के बारे में अधिक जानेंगे।
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
अनुशंसित पाठ
- चौड़ाई पहली खोज (BFS) C ++ प्रोग्राम एक ग्राफ या ट्री को पार करने के लिए
- बाइनरी सर्च ट्री सी ++: BST कार्यान्वयन और उदाहरण के साथ संचालन
- बी ट्री और बी + ट्री डेटा संरचना C ++ में
- शुरुआती के लिए गहराई से ग्रहण ट्यूटोरियल
- सी + + में बाइनरी ट्री डेटा संरचना
- C ++ में ग्राफ़ इम्प्लिमेंटेशन, आसन्न सूची का उपयोग करना
- AVL ट्री और ढेर डेटा संरचना C ++ में
- 12 सर्वश्रेष्ठ लाइन ग्राफ निर्माता उपकरण तेजस्वी रेखा रेखांकन बनाने के लिए (2021 RANKINGS)