डेप्थ-फ़र्स्ट सर्च (DFS)

एक रास्ते पर जितना हो सके उतनी गहराई तक जाकर, फिर पिछले मोड़ पर लौटकर ग्राफ़ को खोजता है। स्क्रीन पर दिखने वाला स्टैक वही रास्ता है।

समय O(V + E)
मेमोरी O(V)
स्टैक का उपयोग करता है

इनका मतलब क्या है?

वर्टेक्स: ग्राफ़ का एक बिंदु, जिसे यहां अक्षर वाले गोले के रूप में दिखाया गया है।
एज: दो वर्टेक्स को जोड़ने वाली रेखा। यहां आप इस पर दोनों ओर चल सकते हैं।
पड़ोसी: वे वर्टेक्स जो किसी वर्टेक्स से एक एज द्वारा जुड़े हैं। इन्हें वर्णमाला के क्रम में देखा जाता है।
क्यू: जो पहले आया, वह पहले निकलता है। BFS हमेशा वह वर्टेक्स लेता है जो सबसे ज़्यादा देर से इंतज़ार कर रहा है।
स्टैक: जो आखिर में आया, वह पहले निकलता है। DFS हमेशा उस वर्टेक्स से आगे बढ़ता है जिस तक वह आखिर में पहुंचा।
V और E: वर्टेक्स और एज की संख्या। O(V + E) का मतलब है कि हर वर्टेक्स और हर एज को तय बार ही संभाला जाता है।

0 / 60 चरण

स्टैक पर
मौजूदा
पूरा
खोज ट्री की एज
छोड़ी गई एज

गति 8 चरण / सेकंड

स्पेस: चलाएं या रोकें। बाएं और दाएं ऐरो: चरण दर चरण। Home और End: सीधे जाएं।

इसे आज़माएं: चक्र वाला ग्राफ़ चुनें। हर डैश वाली एज ऐसे वर्टेक्स पर लौटती है जो पहले से स्टैक पर है या पूरा हो चुका है: वह एज एक चक्र पूरा करती है।

यह कैसे काम करता है

DFS उस पहले पड़ोसी पर खुद को कॉल करता है जिसे उसने अभी तक नहीं देखा, फिर उस वर्टेक्स के पहले नए पड़ोसी पर, और इसी तरह आगे। जब किसी वर्टेक्स का कोई नया पड़ोसी नहीं बचता, तो उसकी कॉल खत्म होती है और DFS एक चरण पीछे जाकर वहां का अगला पड़ोसी आज़माता है। खुली कॉल एक स्टैक बनाती हैं, जो हमेशा शुरुआत से मौजूदा वर्टेक्स तक का रास्ता होता है। वर्टेक्स के पास की संख्या बताती है कि उसे किस क्रम में विज़िट किया गया।

यह कब सही विकल्प है

DFS तब इस्तेमाल करें जब जानना हो कि कहां-कहां पहुंचा जा सकता है, चक्र ढूंढने हों, भूलभुलैया में रास्ता चलना हो या एक-दूसरे पर निर्भर कामों को क्रम में लगाना हो। यह सबसे छोटा रास्ता नहीं ढूंढता।