ग्राफ ट्रैवर्सल
ग्राफ ट्रैवर्सल व्यवस्थित रूप से एक ग्राफ के शीर्षों और किनारों का दौरा करता है; ब्रेड्थ-फर्स्ट सर्च स्तर-दर-स्तर अन्वेषण करता है जबकि डेप्थ-फर्स्ट सर्च पीछे हटने से पहले यथासंभव गहराई तक अन्वेषण करता है, और साथ में वे अधिकांश ग्राफ एल्गोरिदम का आधार बनते हैं।
Definition
ग्राफ ट्रैवर्सल एक ग्राफ के प्रत्येक शीर्ष का दौरा करने (और प्रत्येक किनारे की जांच करने) की प्रक्रिया है जो एक व्यवस्थित क्रम में होती है; ब्रेड्थ-फर्स्ट सर्च एक स्रोत से दूरी के क्रम में शीर्षों का दौरा करता है, और डेप्थ-फर्स्ट सर्च पीछे हटने से पहले प्रत्येक पथ को उसके अंत तक अनुसरण करता है।
Scope
यह विषय दो मौलिक ग्राफ-खोज रणनीतियों, ब्रेड्थ-फर्स्ट सर्च (BFS) और डेप्थ-फर्स्ट सर्च (DFS), उनके क्यू- और स्टैक-आधारित कार्यान्वयन, और उनके द्वारा प्रकट की जाने वाली संरचनात्मक जानकारी — पहुंच योग्यता, जुड़े हुए घटक, भारहीन ग्राफ में सबसे छोटे पथ, टोपोलॉजिकल ऑर्डरिंग, चक्र का पता लगाना, और दृढ़ता से जुड़े हुए घटक — को शामिल करता है। इसमें भारित सबसे छोटे पथ और प्रवाह की समस्याएं शामिल नहीं हैं, जो ट्रैवर्सल पर आधारित हैं लेकिन अलग से मानी जाती हैं।
Core questions
- BFS और DFS शीर्षों का दौरा करने के क्रम में कैसे भिन्न होते हैं, और प्रत्येक क्या प्रकट करता है?
- BFS एक भारहीन ग्राफ में सबसे छोटे पथों की गणना कैसे करता है?
- DFS टोपोलॉजिकल सॉर्टिंग, चक्र का पता लगाने और घटक अपघटन को कैसे सक्षम बनाता है?
- दोनों ट्रैवर्सल शीर्षों और किनारों की संख्या में रैखिक समय में क्यों चलते हैं?
- शीर्षों को दोबारा देखने से बचने के लिए विज़िट किए गए मार्कर और फ्रंटियर संरचनाओं का उपयोग कैसे किया जाता है?
Key concepts
- ब्रेड्थ-फर्स्ट सर्च (BFS)
- डेप्थ-फर्स्ट सर्च (DFS)
- विज़िट किया गया सेट
- क्यू और स्टैक फ्रंटियर
- जुड़े हुए घटक
- टोपोलॉजिकल सॉर्ट
- चक्र का पता लगाना
- दृढ़ता से जुड़े हुए घटक
Key theories
- ब्रेड्थ-फर्स्ट सर्च और भारहीन सबसे छोटे पथ
- BFS एक क्यू का उपयोग करके स्रोत से दूरी के गैर-घटते क्रम में शीर्षों का दौरा करता है, इसलिए यह रैखिक समय में स्रोत से प्रत्येक पहुंच योग्य शीर्ष तक किनारों की न्यूनतम संख्या की गणना करता है।
- डेप्थ-फर्स्ट सर्च और रैखिक ग्राफ एल्गोरिदम
- DFS, अपनी खोज और समापन समय और किनारे के वर्गीकरण के साथ, टोपोलॉजिकल सॉर्टिंग, चक्र का पता लगाने, और दृढ़ता से जुड़े हुए घटकों को खोजने के लिए रैखिक-समय एल्गोरिदम प्रदान करता है, जैसा कि टार्जन द्वारा व्यवस्थित किया गया है।
Clinical relevance
ट्रैवर्सल एल्गोरिदम हर जगह हैं: BFS भारहीन नेटवर्क में सबसे कम हॉप गणना पाता है और वेब क्रॉलर और पीयर-टू-पीयर ब्रॉडकास्ट का आधार है; DFS टोपोलॉजिकल सॉर्ट, डेडलॉक डिटेक्शन, भूलभुलैया और पहेली को सुलझाने, और सामाजिक और जैविक नेटवर्क में घटक विश्लेषण के माध्यम से निर्भरता समाधान और बिल्ड सिस्टम को संचालित करता है।
History
ब्रेड्थ-फर्स्ट सर्च मूर के 1959 के भूलभुलैया रूटिंग पर काम और संबंधित स्वतंत्र प्रयासों से संबंधित है। डेप्थ-फर्स्ट सर्च को रॉबर्ट टार्जन द्वारा 1972 में कठोर एल्गोरिथम आधार पर रखा गया था, जिनके दृढ़ता से जुड़े हुए घटकों और बाइकोनेक्टिविटी के लिए रैखिक-समय एल्गोरिदम ने DFS को एक शक्तिशाली सामान्य उपकरण के रूप में प्रदर्शित किया।
Key figures
- Robert Tarjan
- Edward F. Moore
- John Hopcroft
Related topics
Seminal works
- tarjan1972
- cormen2009
Frequently asked questions
- मुझे DFS के बजाय BFS का उपयोग कब करना चाहिए?
- जब आपको किनारों की संख्या के संदर्भ में सबसे छोटे पथ की आवश्यकता हो या किसी स्रोत से दूरी के क्रम में ग्राफ का अन्वेषण करना हो, तो BFS का उपयोग करें। संरचना के बारे में समस्याओं के लिए DFS का उपयोग करें — टोपोलॉजिकल ऑर्डरिंग, चक्र का पता लगाना, जुड़े हुए या दृढ़ता से जुड़े हुए घटक — जहाँ गहराई से अन्वेषण करना और पीछे हटना स्वाभाविक है।
- BFS और DFS दोनों रैखिक समय क्यों हैं?
- प्रत्येक शीर्ष को एक बार विज़िट किया जाता है और संसाधित किया जाता है, और प्रत्येक किनारे की एक स्थिर संख्या में जांच की जाती है, इसलिए कुल कार्य शीर्षों की संख्या और किनारों की संख्या के अनुपात में होता है, जिसे O(V + E) लिखा जाता है।