मुख्य रूप से डीएफएस का उपयोग ग्राफ में चक्र खोजने के लिए किया जाता है, न कि बीएफएस। किसी भी कारण से? पेड़/ग्राफ़ को घुमाने के दौरान दोनों नोड पहले ही देख चुके हैं।ग्राफ़ में चक्र खोजने के लिए डीएफएस और बीएफएस क्यों नहीं
गहराई पहली खोज चौड़ाई पहली खोज से अधिक स्मृति कुशल है जितनी जल्दी आप बैकट्रैक कर सकते हैं। अगर आप कॉल स्टैक का उपयोग करते हैं तो इसे कार्यान्वित करना भी आसान है, लेकिन यह स्टैक को बहने वाले सबसे लंबे रास्ते पर निर्भर करता है।
यदि आपका ग्राफ directed है तो आपको याद रखना होगा कि क्या आपने नोड का दौरा किया है या नहीं, बल्कि यह भी कि आप वहां कैसे पहुंचे। अन्यथा आपको लगता है कि आपको एक चक्र मिला है लेकिन हकीकत में आपके पास दो अलग-अलग पथ हैं-> बी लेकिन इसका मतलब यह नहीं है कि पथ बी-> ए है। उदाहरण के लिए, 
आप BFS 0 से शुरू करते हैं, इसका पता लगाया जाएगा के रूप में चक्र मौजूद है, लेकिन वास्तव में कोई चक्र है।
गहराई से पहली खोज के साथ आप नोड्स को चिह्नित कर सकते हैं जैसे आप उतरते हैं और उन्हें बैकट्रैक के रूप में चिह्नित करते हैं। इस एल्गोरिदम पर प्रदर्शन सुधार के लिए टिप्पणियां देखें।
best algorithm for detecting cycles in a directed graph के लिए आप Tarjan's algorithm देख सकते हैं।
(मेमोरी कुशल है क्योंकि आप जल्द से जल्द बैकट्रैक प्राप्त करते हैं, और इसे कार्यान्वित करना आसान है क्योंकि आप केवल स्टैक को स्पष्ट रूप से बनाए रखने की बजाय खुली सूची को संग्रहीत करने की देखभाल कर सकते हैं।) – Amber
आईएमओ, यह केवल तभी आसान है जब आप पूंछ पर भरोसा कर सकें प्रत्यावर्तन। डबल पथ परिदृश्य को इंगित करने के लिए –
+1। –
आप एक पेड़ में एक यादृच्छिक स्थान पर एक चक्र देते हैं, तो डीएफएस आधा चक्र जब यह आधा पेड़ के बारे में कवर किया जाता है हिट करने के लिए करते हैं, और आधे समय यह पहले से ही चल गया होगा जहां चक्र चला जाता है, और वह समय नहीं होगा (और इसे पेड़ के आधे हिस्से में औसतन मिलेगा), इसलिए यह पेड़ के औसत 0.5 * 0.5 + 0.5 * 0.75 = 0.625 पर मूल्यांकन करेगा।
यदि आप एक पेड़ में एक यादृच्छिक स्थान पर एक चक्र डालते हैं, तो बीएफएस केवल चक्र को हिट करेगा जब उस गहराई पर पेड़ की परत का मूल्यांकन किया जाएगा। इस प्रकार, आप आमतौर पर संतुलन बाइनरी पेड़ की पत्तियों का मूल्यांकन करने के लिए समाप्त होते हैं, जो आम तौर पर पेड़ के अधिक मूल्यांकन का परिणाम देते हैं। विशेष रूप से, समय के 3/4 पेड़ की पत्तियों में से कम से कम दो लिंक दिखाई देते हैं, और उन मामलों पर आपको पेड़ के औसत 3/4 (यदि कोई लिंक है) या 7/पेड़ के 8 (यदि दो हैं), तो आप पहले से ही 1/2 * 3/4 + 1/4 * 7/8 = (7 + 12)/32 = 21/32 = की खोज की उम्मीद कर रहे हैं 0.656 ... पेड़ के नोड से दूर एक चक्र के साथ एक पेड़ खोजने की लागत को जोड़ने के बिना पेड़ के।
इसके अलावा, डीएफएस बीएफएस की तुलना में लागू करना आसान है। तो यह तब तक उपयोग करने वाला है जब तक कि आप अपने चक्रों के बारे में कुछ नहीं जानते (उदाहरण के लिए चक्र उस रूट के पास होने की संभावना है जहां से आप खोज करते हैं, जिस बिंदु पर बीएफएस आपको लाभ देता है)।
वहां बहुत सारे जादू संख्याएं हैं । मैं "डीएफएस तेज़ है" तर्क से असहमत हूं। यह पूरी तरह से इनपुट पर निर्भर करता है, और इस मामले में किसी भी इनपुट की तुलना में कोई इनपुट अधिक आम नहीं है। – IVlad
@Vlad - संख्याएं जादू नहीं हैं। वे साधन हैं, ऐसे में कहा गया है, और मैंने जो धारणाएं दी हैं, उनकी गणना करने के लिए लगभग तुच्छ हैं। यदि मतलब से अनुमान लगाना एक बुरा अनुमान है, तो यह एक वैध आलोचना होगी। (और मैंने स्पष्ट रूप से कहा है कि यदि आप संरचना के बारे में धारणाएं बना सकते हैं, तो उत्तर बदल सकता है।) –
संख्या जादुई हैं क्योंकि उनका कोई मतलब नहीं है। आपने एक मामला लिया है जो डीएफएस बेहतर है और उन परिणामों को सामान्य मामले में निकाला गया है। आपके बयान निराधार हैं: "डीएफएस चक्र को हिट करेगा जब यह आधा पेड़ ढक जाएगा": साबित करें। उल्लेख नहीं है कि आप एक पेड़ में चक्र के बारे में बात नहीं कर सकते हैं। एक पेड़ में परिभाषा के अनुसार चक्र नहीं होता है। मैं बस नहीं देखता कि आपका मुद्दा क्या है। डीएफएस एक रास्ता तय करेगा जब तक कि यह एक मृत अंत तक नहीं पहुंच जाता है, इसलिए आपके पास यह जानने का कोई तरीका नहीं है कि कितना ग्राफ (पेड़ नहीं) यह औसतन अन्वेषण करेगा। आपने अभी एक यादृच्छिक मामला चुना है जो कुछ भी साबित नहीं करता है। – IVlad
ग्राफ़ अप्रत्यक्ष होने पर एक बीएफएस उचित हो सकता है (बीएफएस का उपयोग करके एक कुशल एल्गोरिदम दिखाने में मेरा अतिथि बनें जो निर्देशित ग्राफ में चक्र की रिपोर्ट करेगा!), जहां प्रत्येक "क्रॉस एज" एक चक्र को परिभाषित करता है। यदि क्रॉस एज {v1, v2} है, और रूट (बीएफएस पेड़ में) जिसमें उन नोड्स हैं r है, तो चक्र r ~ v1 - v2 ~ r (~ एक पथ है, - एक एकल किनारा है), जिसे डीएफएस में लगभग आसानी से रिपोर्ट किया जा सकता है ।
बीएफएस का उपयोग करने का एकमात्र कारण यह होगा कि अगर आपको पता है कि आपके (अप्रत्यक्ष) ग्राफ में लंबे पथ और छोटे पथ कवर (दूसरे शब्दों में, गहरे और संकीर्ण) होने जा रहे हैं। उस स्थिति में, बीएफएस को डीएफएस के ढेर (निश्चित रूप से अभी भी रैखिक दोनों) की तुलना में इसकी कतार के लिए आनुपातिक रूप से कम स्मृति की आवश्यकता होगी।
अन्य सभी मामलों में, डीएफएस स्पष्ट रूप से विजेता है। यह निर्देशित और अप्रत्यक्ष ग्राफ दोनों पर काम करता है, और चक्रों की रिपोर्ट करना तुच्छ है - पूर्वजों से वंश तक किसी भी पिछड़े किनारे को बस संगत करें, और आपको चक्र मिल जाएगा। सब कुछ, इस समस्या के लिए बीएफएस की तुलना में काफी बेहतर और व्यावहारिक।
बीएफएस चक्र खोजने में निर्देशित ग्राफ के लिए काम नहीं करेगा। एक ग्राफ में ए से बी के पथ के रूप में ए-> बी और ए-> सी-> बी पर विचार करें। बीएफएस कहेंगे कि बी के दौरे के रास्ते में से एक के साथ जाने के बाद। अगले मार्ग की यात्रा करते समय यह कहेंगे कि चिह्नित नोड बी फिर से पाया गया है, इसलिए, एक चक्र है। स्पष्ट रूप से यहां कोई चक्र नहीं है।
क्या आप समझा सकते हैं कि डीएफएस स्पष्ट रूप से कैसे पहचान करेगा कि चक्र आपके उदाहरण में मौजूद नहीं है। मैं मानता हूं कि चक्र प्रदान किए गए उदाहरण में मौजूद नहीं है। लेकिन अगर हम ए-> बी से जाते हैं और फिर ए-> सी-> बी हम करेंगे पाते हैं कि बी पहले से ही देखा गया था और इसके माता-पिता ए नहीं हैं ... और मैंने पढ़ा है कि डीएफएस मौजूदा नोड के साथ पहले से देखे गए तत्व के माता-पिता की तुलना करके चक्र का पता लगाएगा, जिस दिशा से हम इस पल में जांच कर रहे हैं। मुझे डीएफएस गलत लगता है और क्या? – smasher
जो आपने यहां दिखाया है वह यह है कि यह विशेष कार्यान्वयन काम नहीं करता है, न कि यह बीएफएस के साथ असंभव है। वास्तव में, यह * संभव है, हालांकि यह अधिक काम और स्थान लेता है। – Prune
@Prune: सभी धागे (मुझे लगता है) यहां साबित करने की कोशिश कर रहे हैं कि बीएफएस चक्रों का पता लगाने के लिए काम नहीं करेगा। यदि आप साबित करते हैं कि साबित करने के लिए आपको सबूत देना चाहिए। बस यह कहकर कि प्रयास अधिक से अधिक नहीं हैं –
यह साबित करने के लिए कि एक ग्राफ चक्रीय है, आपको केवल यह साबित करने की आवश्यकता है कि इसमें एक चक्र है (किनारे सीधे या परोक्ष रूप से ओर इशारा करते हैं)।
डीएफएस में हम एक समय में एक कशेरुक लेते हैं और जांचते हैं कि इसमें चक्र है या नहीं। जैसे ही एक चक्र पाया जाता है हम अन्य शिखरों की जांच छोड़ सकते हैं।
बीएफएस में हमें कई चरम किनारों का एक साथ ट्रैक रखने की आवश्यकता है और अंत में नहीं, अंत में आप यह पता लगाते हैं कि इसमें चक्र है या नहीं। ग्राफ के आकार के रूप में बीएफएस को डीएफएस की तुलना में अधिक जगह, गणना और समय की आवश्यकता होती है।
यह निर्भर करता है कि यदि आप रिकर्सिव या पुनरावृत्ति कार्यान्वयन के बारे में बात कर रहे हैं।
रिकर्सिव-डीएफएस दो बार प्रत्येक नोड पर जाता है। इटरेटिव-बीएफएस एक बार प्रत्येक नोड का दौरा करता है।
यदि आप एक चक्र का पता लगाना चाहते हैं, तो आपको नोड्स पर "शुरू" करते समय और जब आप नोड के साथ "खत्म" करते हैं तो दोनों को अपने आसन्नताओं को जोड़ने से पहले और बाद में नोड्स की जांच करने की आवश्यकता होती है।
इसके लिए इटरेटिव-बीएफएस में अधिक काम की आवश्यकता है ताकि अधिकांश लोग रिकर्सिव-डीएफएस चुन सकें।
ध्यान दें कि Iterative-DFS के साथ एक सरल कार्यान्वयन, कहें, std :: स्टैक में Iterative-BFS के समान समस्या है। उस स्थिति में, जब आप नोड पर काम खत्म करते हैं तो आपको ट्रैक करने के लिए डमी तत्वों को स्टैक में रखना होगा।
कैसे Iterative-डीएफएस अतिरिक्त कार्य की आवश्यकता है के बारे में अधिक जानकारी के लिए इस सवाल का जवाब देखें निर्धारित करने के लिए जब आप "खत्म" एक नोड (TopoSort के संदर्भ में जवाब) के साथ:
Topological sort using DFS without recursion
उम्मीद है कि यही कारण है कि बताते हैं कि लोग उन समस्याओं के लिए रिकर्सिव-डीएफएस का पक्ष लेते हैं जहां आपको यह निर्धारित करने की आवश्यकता होती है कि जब आप नोड को संसाधित करते हैं।
क्या आपका ग्राफ निर्देशित या अप्रत्यक्ष है? –
निर्देशित ग्राफ में, केवल एक चक्र का पता लगाने के लिए डीएफएस का उपयोग किया जा सकता है; लेकिन अप्रत्यक्ष ग्राफ में दोनों का उपयोग किया जा सकता है। – Hengameh