DFS भी BFS की तरह ग्राफ डेटा स्ट्रक्चर को travers तथा search करने की एक अल्गोरिथम है। BFS में नोड्स को depth wise (गहराई से) विजिट किया जाता है। डेटा स्ट्रक्चर में DFS को implement करने के लिए stack का प्रयोग किया जाता है।
DFS एक recursive अल्गोरिथम है जो कि backtracking के सिधांत पर कार्य करती है। नेटवर्कों को analyze करने, routes को map करने तथा अन्य कंप्यूटर विज्ञानं की परेशानियों को solve करने के लिए DFS का प्रयोग किया जाता है।
DFS Algorithm
DFS में हम सबसे पहले शुरूआती node को stack के द्वारा विजिट करते है. फिर इसकी समस्त adjacent nodes को stack में डालकर, stack को top में स्थित नोड को विजिट करके, उसके समस्त adjacent node को stack में डाल देते है और प्रक्रिया तब तक दोहराते जब तक कि stack खाली नहीं हो जाता है।
इसकी अल्गोरिथम को निम्नलिखित उदाहरण के द्वारा समझते है.
स्टेप 1. stack को intialize किया जाता है।
स्टेप 2. नोड A को visited मार्क करते है और उसे स्टैक में डालते हैं. नोड A के तीन adjacent नोड है B, C, तथा D. हम इनमें से किसी भी नोड को चुन सकते है. हम alphabetical क्रम में चुनेंगें।
स्टेप 3. नोड B को visited मार्क करेंगे और स्टैक में डालेंगे. अब B के किसी unvisited adjacent नोड्स को select करेंगे. B के adjacent नोड्स A तथा E है चूँकि A को पहले ही विजिट कर लिया है तो हम E को select करेंगे।
स्टेप 4. E को विजिट करेंगे और इसे visited मार्क करेंगे और इसे stack में डाल देंगे। यहाँ पर नोड E के दो adjacent नोड C तथा D है दोनों unvisited है तो हम C को select करेंगे. (alphabetical क्रम में.)
स्टेप 5. हम c को विजिट करेंगे और इसे visited मार्क करेंगे और स्टैक में रख देंगे। यहाँ पर B का कोई unvisited adjacent नोड नहीं है तो इसे stack से निकाल देंगे।
स्टेप 6. अब stack के top पर वापस E है अब देखेंगे कि इसका कोई unvisited adjacent node है या नही। इसका adjacent unvisited नोड D है।
स्टेप 7. अब हम नोड D को विजिट करेंगे और इसे visited मार्क करेंगे और इसे stack में डाल देंगे।
अब विजिट करने के लिए कोई नोड नहीं बचा है अब हम सभी नोड्स को stack में से बाहर निकालेंगे और जब stack empty हो जाएगा तो प्रोग्राम समाप्त हो जाएगा।