आपके ट्रैवर्सल का अंतिम परिणाम सही है, तो आप बहुत करीब हैं। हालांकि, आप विवरण में थोड़ा सा बंद कर रहे हैं।
गहराई में पहली खोज में, आप एक नोड पॉप करेंगे, इसे विज़िट के रूप में चिह्नित करें और इसके अनजान बच्चों को ढेर करें। उस क्रम में। ऑर्डर एक पेड़ के लिए अप्रासंगिक प्रतीत हो सकता है, लेकिन यदि आपके पास चक्र के साथ ग्राफ था, तो आप अनंत लूप में गिर सकते हैं, लेकिन यह एक और चर्चा है।
एल्गोरिदम की आधार रेखा को देखते हुए, आप रूट नोड को स्टैक में धक्का देने के बाद, आप अपना पहला पुनरावृत्ति शुरू करेंगे, तुरंत एपीगोरिदम के अंत तक यह स्टैक पर नहीं रहेगा। आप ए, स्टैक डी, सी और बी को सभी एक बार (या बी, सी और डी) पॉप करेंगे, आप इसे बाएं से दाएं या दाएं से बाएं कर सकते हैं, यह आपकी पसंद है) और ए को विज़िट के रूप में चिह्नित करें। अभी, आपके ढेर में नीचे डी है, बीच में सी और बी शीर्ष पर है।
अगला नोड पॉप बी है। आप एफ और ई को स्टैक में दबाएंगे (मैं आपके जैसा ही आदेश रखूंगा), बी को चिह्नित करने के रूप में चिह्नित किया गया। ढेर, ऊपर से नीचे तक, ई एफ सी डी अगला है, ई पॉप किया गया है, कोई नया नोड जोड़ा गया है और ई को विज़िट के रूप में चिह्नित किया गया है। पाश, जारी रहेगा एफ, सी और डी अंतिम आदेश के लिए एक ही कर ABEFC डी है
मैं तुम्हारा करने के लिए एक समान तरीके से एल्गोरिथ्म को फिर से लिखने की कोशिश करता हूँ:
Push root into stack
Loop until stack is empty
Pop node N on top of stack
Mark N as visited
For each children M of N
If M has not been visited (M.visited() == false)
Push M on top of stack
मैं जीता चौड़ाई पहली खोज के लिए विवरण में नहीं जाना है, एल्गोरिदम बिल्कुल वही है। अंतर डेटा संरचना में है और यह कैसे व्यवहार करता है। एक कतार फीफो (फर्स्ट इन फर्स्ट आउट) है, और इसके कारण, आप निम्न स्तरों में नोड्स पर जाने से पहले उसी स्तर पर सभी नोड्स पर जायेंगे।
नोट: डीएफएस का उपयोग करने के लिए यह बहुत ही कुशल या वास्तविक समय नहीं है क्योंकि संभावनाओं की मात्रा बहुत बड़ी हो जाती है, इसलिए आप कुछ गणनाओं के आधार पर उचित कदम उठाने के लिए बीएफएस का उपयोग करते हैं। यहां काफी प्रासंगिक नहीं है लेकिन आप एआई के लिए मिनिमैक्स एल्गोरिदम में देखना चाहते हैं क्योंकि यह अपेक्षाकृत सरल है और एक चाल के साथ आने के लिए संभावनाओं की मात्रा को कम करने का प्रदर्शन करता है (आमतौर पर टिक-टैक-टो में)। – wazy
@wazy यह डेटा पर निर्भर करेगा।क्या होगा यदि ग्राफ प्रति ऊंचाई की तुलना में प्रति स्तर अधिक नोड्स है? –
मुझे यह कहने से नफरत है कि "निर्भर करता है" लेकिन यह बहुत निर्भर है कि आप "जल्दी" (या कम से कम प्रयास करने और आवश्यक रूप से इष्टतम नहीं) का समाधान ढूंढने की कोशिश कर रहे हैं या आप हर संभव समाधान/संयोजन का मूल्यांकन करने की कोशिश कर रहे हैं। – wazy