breadth first search c program traverse graph
यह ट्यूटोरियल C ++ में ब्रेडथ फर्स्ट सर्च को शामिल करता है जिसमें ग्राफ या ट्री ट्रैवर्सेड ब्रेड वाइट है। आप BFS एल्गोरिथम और कार्यान्वयन भी सीखेंगे:
यह स्पष्ट C ++ ट्यूटोरियल आपको ट्रैवर्सल तकनीकों की एक विस्तृत व्याख्या देगा जो एक पेड़ या ग्राफ पर किया जा सकता है।
ट्रैवर्सल वह तकनीक है जिसके उपयोग से हम ग्राफ और पेड़ के प्रत्येक नोड पर जाते हैं। ट्रैवर्सल्स के दो मानक तरीके हैं।
- चौड़ाई-पहली खोज (BFS)
- गहराई-पहली खोज (DFS)
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
Android के लिए अच्छा मुफ्त संगीत डाउनलोडर
आप क्या सीखेंगे:
चौड़ाई पहली खोज (BFS) तकनीक C ++ में
इस ट्यूटोरियल में, हम विस्तार से चर्चा करेंगे।
चौड़ाई-प्रथम ट्रैवर्सल तकनीक में ग्राफ या ट्री को चौड़ाई-वार माना जाता है। यह तकनीक क्रास डेटा नोड्स को नोड्स या नोड्स को संग्रहीत करने के लिए उपयोग करती है और यह भी निर्धारित करने के लिए कि आगे कौन सा शीर्ष / नोड लिया जाना चाहिए।
चौड़ाई-पहले एल्गोरिथ्म रूट नोड के साथ शुरू होता है और फिर सभी आसन्न नोड्स का पता लगाता है। फिर, यह निकटतम नोड का चयन करता है और अन्य सभी अनविसीड नोड्स की खोज करता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि ग्राफ़ के सभी नोड्स की खोज नहीं हो जाती।
चौड़ाई-पहली खोज एल्गोरिथम
नीचे दिए गए बीएफएस तकनीक के लिए एल्गोरिदम है।
जी को एक ग्राफ के रूप में समझें जिसे हम बीएफएस एल्गोरिथ्म का उपयोग करते हुए आगे बढ़ने वाले हैं।
बता दें कि ग्राफ का S / रूट नोड है।
- चरण 1: नोड एस के साथ शुरू करें और इसे कतार में संलग्न करें।
- चरण 2: ग्राफ़ में सभी नोड्स के लिए निम्न चरणों को दोहराएं।
- चरण 3: Squeue S और इसे संसाधित करें।
- चरण 4: एस के सभी आसन्न नोड्स को संलग्न करें और उन्हें संसाधित करें।
- [समाप्ति की समाप्ति]
- चरण 6: बाहर जाएं
स्यूडोकोड
बीएफएस तकनीक के लिए छद्म कोड नीचे दिया गया है।
Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end
दृष्टांत के साथ ट्रावेल्स
मान लें कि शुरुआती नोड या स्रोत नोड है। सबसे पहले, हम इसे विज़िट की गई कतार में और उसके सभी समीपवर्ती नोड्स को कतार में शामिल करते हैं।
अगला, हम प्रक्रिया करने के लिए आसन्न नोड्स में से एक लेते हैं अर्थात् 1. हम इसे कतार से हटाकर विज़िट के रूप में चिह्नित करते हैं और इसके आसन्न नोड्स को कतार में डालते हैं (2 और 3 पहले से ही कतार में)। जैसा कि 0 पहले से ही दौरा किया गया है, हम इसे अनदेखा करते हैं।
पीसी प्रदर्शन में सुधार करने के लिए सबसे अच्छा मुफ्त सॉफ्टवेयर
अगला, हम नोड 2 को समाप्त करते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। फिर, इसके आसन्न नोड 4 को कतार में जोड़ा जाता है।
अगला, हम कतार से 3 को हटाते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। नोड 3 में केवल एक आसन्न नोड है, अर्थात 0 जो पहले से ही दौरा किया गया है। इसलिए, हम इसे अनदेखा करते हैं।
इस स्तर पर, केवल नोड 4 कतार में मौजूद है। इसकी आसन्न नोड 2 पहले से ही देखी गई है, इसलिए हम इसे अनदेखा करते हैं। अब हम 4 को चिह्नित करते हैं।
इसके बाद, विज़िट की गई सूची में मौजूद अनुक्रम दिए गए ग्राफ की चौड़ाई-प्रथम अनुक्रमणिका है।
यदि हम दिए गए ग्राफ और ट्रैवर्सल अनुक्रम का निरीक्षण करते हैं, तो हम यह नोटिस कर सकते हैं कि बीएफएस एल्गोरिथ्म के लिए, हम वास्तव में ग्राफ चौड़ाई के अनुसार चलते हैं और फिर अगले स्तर पर जाते हैं।
बीएफएस कार्यान्वयन
#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list [V]; } void DiGraph::addEdge(int v, int w) { adjList[v].push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool[V]; for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList[s].begin(); i != adjList[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '< आउटपुट:
खोलने .7z फ़ाइलें मैक पर
दिए गए ग्राफ के लिए चौड़ाई-प्रथम त्रैमासिक (नोड शुरू करने के साथ):
0 1 2 3 4
हमने उपरोक्त कार्यक्रम में बीएफएस लागू किया है। ध्यान दें कि ग्राफ एक आसन्न सूची के रूप में है और फिर हम सूची के माध्यम से पुनरावृति करने के लिए एक बीटर का उपयोग करते हैं और बीएफएस करते हैं।
हमने उसी ग्राफ का उपयोग किया है जो हमने ट्रैवर्सल सीक्वेंस की तुलना करने के लिए प्रोग्राम के इनपुट के रूप में चित्रण प्रयोजनों के लिए उपयोग किया था।
रनटाइम विश्लेषण
यदि V कोने की संख्या है और E एक ग्राफ के किनारों की संख्या है, तो BFS के लिए समय जटिलता व्यक्त की जा सकती है O (| V | + | E |) । यह कहने के बाद, यह उस डेटा संरचना पर भी निर्भर करता है जिसका उपयोग हम ग्राफ़ का प्रतिनिधित्व करने के लिए करते हैं।
यदि हम आसन्न सूची (जैसे हमारे कार्यान्वयन में) का उपयोग करते हैं, तो समय जटिलता है O (| V | + | E |) |
यदि हम आसन्न मैट्रिक्स का उपयोग करते हैं, तो समय जटिलता है O (V ^ 2) ।
उपयोग किए गए डेटा संरचनाओं के अलावा, यह भी एक कारक है कि क्या ग्राफ घनी आबादी वाला है या कम आबादी वाला है।
जब कोने की संख्या किनारों की संख्या से अधिक हो जाती है, तो ग्राफ को काफी हद तक जुड़ा हुआ कहा जाता है क्योंकि कई डिस्कनेक्ट किए गए कोने होंगे। इस स्थिति में, ग्राफ की समय जटिलता O (V) होगी।
दूसरी ओर, कभी-कभी ग्राफ़ में कोने की संख्या की तुलना में किनारों की संख्या अधिक हो सकती है। ऐसे में ग्राफ को घनी आबादी वाला कहा जाता है। इस तरह के ग्राफ की समय जटिलता O (E) है।
यह निष्कर्ष निकालने के लिए कि ओ क्या है (O | (V | + | E |) का अर्थ है कि यह ग्राफ घनी या कम आबादी वाला है, इस बात पर निर्भर करता है कि डोमिनेटिंग फैक्टर यानी किनारों या कोने का निर्धारण ग्राफ के समय की जटिलता के अनुसार होगा।
बीएफएस ट्रैवर्सल के अनुप्रयोग
- कचरा इकठा करना: कचरा संग्रहण तकनीक, 'चेनी के एल्गोरिथ्म' कचरा संग्रह की नकल करने के लिए पहले-पहले ट्रैवर्सल का उपयोग करता है।
- प्रसारण नेटवर्क में: एक पैकेट प्रसारण नोड नेटवर्क में सभी नोड्स तक पहुंचने के लिए एक नोड से दूसरे नोड तक बीएफएस तकनीक का उपयोग करता है।
- GPS नेविगेशन: हम GPS नेविगेशन में BFS का उपयोग आसन्न या पड़ोसी स्थान नोड्स को खोजने के लिए कर सकते हैं।
- सोशल नेटवर्किंग वेबसाइट्स: किसी व्यक्ति a P ’को देखते हुए, हम BFS का उपयोग करते हुए d से the d’ तक की दूरी के भीतर सभी लोगों को पा सकते हैं।
- पीयर टू पीयर नेटवर्क: फिर से बीएफएस का उपयोग पीयर टू पीयर नेटवर्क में सभी आसन्न नोड्स को खोजने के लिए किया जा सकता है।
- सबसे कम पथ और न्यूनतम भारित ट्री अन-वेटेड ग्राफ में: बीएफएस तकनीक का उपयोग सबसे कम पथ को खोजने के लिए किया जाता है, यानी बिना भारित ग्राफ में किनारों की सबसे कम संख्या वाला पथ। इसी तरह, हम अन-वेटेड ग्राफ में BFS का उपयोग करते हुए न्यूनतम फैले हुए वृक्ष भी पा सकते हैं।
निष्कर्ष
चौड़ाई-पहली खोज तकनीक एक ऐसी विधि है जिसका उपयोग किसी ग्राफ या पेड़ के सभी नोड्स को चौड़ाई-वार तरीके से करने के लिए किया जाता है।
इस तकनीक का उपयोग ज्यादातर ग्राफ के नोड्स या अनुप्रयोगों में सबसे छोटा रास्ता खोजने के लिए किया जाता है, जो हमें नेटवर्क जैसे प्रत्येक आसन्न नोड पर जाने की आवश्यकता होती है।
=> फ्री सी ++ कोर्स के लिए यहां क्लिक करें।
अनुशंसित पाठ
- बाइनरी सर्च ट्री सी ++: BST कार्यान्वयन और उदाहरण के साथ संचालन
- बी ट्री और बी + ट्री डेटा संरचना C ++ में
- C ++ में ग्राफ़ इम्प्लिमेंटेशन, आसन्न सूची का उपयोग करना
- सी + + में बाइनरी ट्री डेटा संरचना
- 12 सर्वश्रेष्ठ लाइन ग्राफ निर्माता उपकरण तेजस्वी रेखा रेखांकन बनाने के लिए [2021 RANKINGS]
- AVL ट्री और ढेर डेटा संरचना C ++ में
- C ++ में पेड़: मूल शब्दावली, ट्रैवर्सल तकनीक और C ++ ट्री प्रकार
- कारण और प्रभाव ग्राफ - डायनेमिक टेस्ट केस राइटिंग टेक्नीक फॉर मैक्सिमम कवरेज फॉर फेयर टेस्ट केसेस