मैं हमेशा मिश्रण करता हूं कि क्या मैं डीएफएस या बीएफएस के लिए स्टैक या कतार का उपयोग करता हूं। क्या कोई यह याद रखने के बारे में कुछ अंतर्ज्ञान प्रदान कर सकता है कि कौन सी एल्गोरिदम डेटा संरचना का उपयोग करता है?मुझे याद है कि डीएफएस और बीएफएस द्वारा कौन सी डेटा संरचनाओं का उपयोग किया जाता है?
कागज के टुकड़े पर एक छोटा ग्राफ बनाएं और उस क्रम के बारे में सोचें जिसमें प्रत्येक कार्यान्वयन में नोड्स संसाधित होते हैं। जिस क्रम में आप नोड्स का सामना करते हैं और जिस क्रम में आप नोड्स को संसाधित करते हैं, वह खोजों के बीच भिन्न होता है?
उनमें से एक स्टैक (गहराई-प्रथम) का उपयोग करता है और दूसरा एक कतार (चौड़ाई-प्रथम) (कम से कम गैर-पुनरावर्ती कार्यान्वयन के लिए) का उपयोग करता है।
बीएफएस पहले निकटतम कोष्ठकों की खोज/प्रक्रिया करता है और फिर स्रोत से बाहर की तरफ जाता है। यह देखते हुए, आप एक डेटा संरचना का उपयोग करना चाहते हैं, जब पूछे जाने वाले आदेश आपको सबसे पुराना तत्व प्रदान करते हैं, जिस क्रम में वे डाले गए थे। एक कतार वह है जो आपको इस मामले में चाहिए क्योंकि यह पहली बार पहली बार (फीफो) है। जबकि एक डीएफएस प्रत्येक शाखा के साथ पहले और फिर ब्रैकट्रैक जितना संभव हो सके खोजता है। इसके लिए, एक स्टैक बेहतर काम करता है क्योंकि यह LIFO (अंतिम-इन-फर्स्ट-आउट)
बीएफएस हमेशा कतार का उपयोग करता है, डीएफएस स्टैक डेटा संरचना का उपयोग करता है। जैसा कि पहले स्पष्टीकरण डीएफएस के बारे में बताता है बैकट्रैकिंग का उपयोग कर रहा है। याद रखें बैकट्रैकिंग केवल स्टैक द्वारा आगे बढ़ सकती है।
बीएफ; चौड़ाई => कतार
Dfs; गहराई => ढेर
उनकी संरचना का संदर्भ लें
मैं इसे अपने मन में बारबेक्यू रखकर याद है। बारबेक्यू 'बी' से शुरू होता है और 'क्यू' जैसी ध्वनि के साथ समाप्त होता है इसलिए बीएफएस -> कतार और शेष वाले डीएफएस -> ढेर। , BFS जबकि
ढेर एक खड़ी संरचना के रूप में कल्पना की है -
कतार आम तौर पर के रूप में संरचना यानी में क्षैतिज, चौड़ाई सोचा जा सकता है/चौड़ाई इसे करने के लिए जिम्मेदार ठहराया जा सकता और इसलिए गहराई - डीएफएस है।
नए शिक्षार्थियों के लिए अच्छा दृश्य क्यू। +1। – displayName
गहराई की पहली खोज Stack का उपयोग करती है, यह याद रखने के लिए कि यह मृत अंत तक पहुंचने पर कहां जाना चाहिए।
DFSS
वर्णमाला क्रम में ले लो ...
.... बी (BFS) ..... सी ...... डी (डीएफएस)। ...
.... क्यू (कतार) ... आर ...... एस (ढेर) ...
मैं इस सवाल का जवाब साझा करना चाहते हैं: https://stackoverflow.com/a/20429574/3221630
बीएफएस लेना और एक स्टैक के साथ कतार को बदलना, डीएफएस के समान विज़िट ऑर्डर को पुन: उत्पन्न करता है, यह वास्तविक डीएफएस एल्गोरिदम की तुलना में अधिक स्थान का उपयोग करता है।
ढेर (प्रथम से LIFO में अंतिम)। डीएफएस के लिए, हम रूट से इसे सबसे दूर तक नोड तक जितना संभव हो सके, यह लिफ़ो के समान विचार है।
कतार (फर्स्ट इन फर्स्ट आउट, फीफो)। बीएफएस के लिए, हम नोड के ऊपरी स्तर पर जाने के बाद, इसे एक स्तर से एक स्तर पर पुनर्प्राप्त करते हैं, हम नोड के निचले स्तर पर जाते हैं, यह फीफो के समान विचार है।
अच्छा अवलोकन :) – RBT