इस पोस्ट में आप (DFS) Depth first search के बारे में पढ़ेंगे, Depth first search in hindi और साथ ही जानेंगे की DFS अल्गोरिथम कैसे काम करता है।
What Is DFS In Hindi | Depth First Search क्या है।
DFS भी BFS की ही तरह एक ग्राफ ट्रेवेर्सल अल्गोरिथम है, और इन दोनों methods द्वारा किसी ग्राफ के vertices थता Edges को visit किया जाता है, लेकिन फर्क सिर्फ इन दोनों के visit करने के तरीके में है। DFS, BFS से उलट किसी ग्राफ, या ट्री को breadthward motion के बजाय Depthward motion में चेक करता है, यानि यह Nodes को चौड़ाई से चेक करने के बजाय गहराई से चेक करता है। DFS में Stack डाटा स्ट्रक्चर का उपयोग होता है, जो की (LIFO) last in first out method को फॉलो करता है।
Depth first search अल्गोरिथम का उपयोग Topological sorting, Nodes के बीच path find करने थता Puzzle solving के लिए किया जाता है। इसके सिद्धांत अनुसार पहले यह start node से शुरू करता है, फिर उसके child node को चेक करता है, और फिर child node के भी child node यानि Start node के (Grand child) को चेक करता है।
इसी प्रकार यह अगले level पर जाता है, और वहां भी वही प्रक्रिया चलती रहती है, जब तक की Child node मिलते रहें, या वह Starting node पर ना पहुँच जाए।
चलिए उदाहरण द्वारा DFS की वर्किंग को समझते हैं।
DFS में यदि रुट नोड को mention नहीं किया गया हो, तो आप किसी भी नोड को Root node के रूप में ले सकते हैं, तो यहाँ पर हम S को रुट नोड लेते हैं।
सबसे पहले Stack को Initialize करेंगे।
stack
अब क्योंकि हमने S को रुट नोड चुना है, तो उसे हम visited मार्क करेंगे और स्टैक में डाल देंगे।
stack
| S |
अब यहाँ पर हम S के unvisited adjacent नोड्स को explore करेंगे। यहाँ पर S के adjacent नोड्स हैं, A, B और C, तो हम क्रम अनुसार पहले नोड A को चुनेंगे, और उसे visited मार्क कर stack में डाल देंगे।
stack
| A |
| S |
यहाँ पर अब हम A के unvisited adjacent नोड्स को explore करेंगे, तो S तथा D दोनों ही A के adjacent नोड हैं, लेकिन S को visit कर लिया गया है, तो हम नोड D को visited मार्क कर स्टैक में डालेंगे।
stack
| D |
| A |
| S |
अब यहाँ पर D के unvisited adjacent नोड हैं, B और C तो हम क्रम अनुसार B को visited मार्क करेंगे और स्टैक में डाल देंगे।
| B |
| D |
| A |
| S |
अब यहाँ पर B का कोई भी unvisited adjacent नोड नहीं है, तो नोड B को stack से Pop out कर देंगे, और backtrack करके D में आ जाएंगे।
stack
| D |
| A |
| S |
यहाँ पर अब D के unvisited adjacent नोड को देखा जाएगा, जो की C है, तो स्टैक में C को ऐड कर दिया जाएगा।
stack
| C |
| D |
| A |
| s |
इसी प्रकार अब C का कोई unvisited adjacent नोड नहीं है, तो C को स्टैक से pop out कर दिया जाएगा, और एक-एक कर सभी nodes को भी unvisited adjacent नोड ना होने पर, स्टैक से pop out कर दिया जाएगा जब तक की स्टैक पूरी तरह से empty ना हो जाए, और स्टैक का empty होना DFS Algorithm को स्टॉप करने का indication होता है।
आपने जाना DFS क्या होता है, (DFS) Depth first search in hindi और यह कैसे काम करता है। हमें उम्मीद है, जानकारी आपको ज्ञानवर्धक लगी होगी, यदि जानकारी आपको अच्छी लगी है, तो इसे अपने दोस्तों के साथ भी शेयर करें।