हैलो मित्रों! इस Article में हम Graph Traversal Technique , Depth First Search के बारेमे जानने वाले है । DFS , Graph Traversal के लिए उपयोग होने वाली बहुत ही आसान तकनीक है।
Depth First Search क्या है ?
इसमें ग्राफ को देखते हुए हमें गहराई से आगे बढ़ना है, जबकि ऐसी कोई संभावना है, यदि नहीं तो हमें बैकट्रैक करना होगा। यहां बैकट्रैक शब्द का अर्थ है कि हमने एक अंत प्राप्त कर लिया है, इसलिए पीछे हटें और दूसरा रास्ता चुनें।
DFS full Form in data structure
DFS Example
आइए DFS को एक उदाहरण की मदद से समजे ।
दिखाए गए ग्राफ पर विचार करें। हमारे पास A से F लेबल वाले 6 नोड्स हैं। अब हम देखते हैं कि ये नोड्स जुड़े हुए हैं और उन्हें पार करने से हम अनंत लूप में फंस सकते हैं।
तो हम इसे कैसे ठीक कर सकते हैं ?
इसका समाधान यह हो सकता है कि प्रत्येक नोड के लिए एक बूलियन विज़िट किया गया Flag हो। यह Flag फ्लैगहोगा यदि हम किसी विशेष नोड पर गए हैं तो यह गलत होगा। चूंकि हमारे पास 1 से अधिक नोड हैं, इसलिए हम ऐसे झंडे की एक सरणी का उपयोग करेंगे और इसे बूलियन विज़िट किया गया सरणी कहेंगे।
आइए हमारी DFS एल्गोरिथम को चलाने के लिए आवश्यक सामग्री को जल्दी से देखें।
हमें एक ग्राफ, एक स्टैक और एक आउटपुट Array की आवश्यकता होगी। शुरू में हमारा Stack खाली होता है और सभी नोड्स पर ध्यान नहीं दिया जाता है।
ध्यान दें कि ऑरेंज और ब्लू ,विज़िट किए गए और न देखे गए नोड्स का प्रतिनिधित्व करते हैं और Algorithm के बेहतर विज़ुअलाइज़ेशन के लिए हमने स्टैक को लंबवत तरीके से दिखाया है।
Step 1 : अब हमारे एल्गोरिथ्म को A लेबल वाले इस शुरुआती शीर्ष के साथ शुरू करते हैं, हम इसे अपने Stack में धकेलते हैं, इसे आउटपुट के रूप में प्रिंट करते हैं और इसे देखे गए को चिह्नित करते हैं।
Stack :
_
_
_
_
A
Output: A
Step 2 : इसके बाद हम A के निकटवर्ती गैर-विजिटेड नोड्स को देखते हैं (B,C) जो मानदंड रखते हैं, हम उनमें से किसी को भी चुन सकते हैं। हम जाएंगे और B को चुनेंगे। नोड बी को स्टैक में चुनें, इसे प्रिंट करें और इसे देखें।
Stack :
_
_
_
B
A
Output : A B
Step 3 : अब हम B. के अनजान आसन्न नोड्स को देखते हैं ,B और नोड E आवश्यक पड़ोसी हैं। हम D चुनते हैं। इसे अपने स्टैक पर पुश करें, इसे प्रिंट करें और इसे विज़िट के रूप में भी चिह्नित करें।
Stack :
_
_
D
B
A
Output : A B D
Step 4 : अब हम D.Vertex E और F के अनजान आसन्न नोड्स को देखते हैं जो हमारे दिए गए मानदंडों को पूरा करते हैं। हम Vertex E चुनते हैं। इसे स्टैक पर पुश करें, इसे प्रिंट करें और इसे देखें।
Stack :
_
E
D
B
A
Output : A B D E
Step 5 : अब E के निकटवर्ती गैर-विजिटेड नोड्स को देखते हैं। हम नोड C और F को एक के रूप में पाते हैं जो दिए गए मानदंडों को धारण करते हैं। हम एफ को स्टैक पर दबाते हैं, इसे प्रिंट करते हैं और उस पर भी जाते हैं।
Stack :
F
E
D
B
A
Output : A B D E F
Step 6 : अब हम F के असंबद्ध आसन्न नोड्स देखते हैं। हम पाते हैं कि सभी आसन्न नोड्स का दौरा किया गया है और इसलिए कोई रास्ता नहीं है। इसलिए हम पीछे हटते हैं। हम Stack के ऊपर से नोड F को पॉप करते हैं।
Stack :
_
E
D
B
A
Step 7 : अब हमारे पास Stack के शीर्ष के रूप में नोड E है। हम ई के अनजान आसन्न नोड्स के लिए देखते हैं। हमें एक नोड मिलता है जो C है। हम इसे अपने स्टैक पर दबाते हैं, इसे प्रिंट करते हैं और इसे विज़िट के रूप में चिह्नित करते हैं।
Stack :
C
E
D
B
A
Output : A B D E F C
Step 8 : अब हम C के निकटवर्ती गैर-विजिटेड नोड को देखते हैं, ऐसे कोई नोड नहीं हैं। इसलिए हम स्टैक से C पॉप करते हैं।
Stack :
_
E
D
B
A
Step 9 : अब हमारे पास Stack के शीर्ष के रूप में E है। E के कोई अनजान आसन्न नोड नहीं हैं, इसलिए हम फिर से स्टैक से E पॉप करते हैं।
Stack :
_
_
D
B
A
Step 10 : अब D आता है और फिर से हम पाते हैं कि नोड D के कोई अनजान पड़ोसी नहीं हैं। इसलिए हम स्टैक से D पॉप करते हैं।
Stack :
_
_
_
B
A
Step 11 : B स्टैक का नया शीर्ष है। हम देखते हैं कि B का कोई भी पड़ोसी नहीं है। इसलिए हम Stack से B पॉप करते हैं।
Stack :
_
_
_
_
A
Step 12 : अब हमारे पास A रह गया है। A के दो पड़ोसियों का दौरा किया गया है और इसलिए हमारे पास नहीं है और Stack से A को पॉप करेंगे।
Stack :
_
_
_
_
_
Output : A B D E F C
अब हम देखते हैं कि हमारा Stack खाली है। यह हमारे एल्गोरिथम को रुकने का संकेत देगा। अब हम एक विराम लेते हैं और देखते हैं कि सभी नोड्स का दौरा कैसे किया जाता है और मुद्रित भी किया जाता है।
Depth First Search ग्राफ़ में प्रत्येक शीर्ष पर जाती है और प्रत्येक नोड के लिए प्रत्येक किनारे की जांच करती है। Depth First Search के लिए समय जटिलता O (V + E) है। यहां वी शीर्ष या नोड्स हैं और E ,Edge हैं।
Conclusion
हमें उम्मीद है की आपको यह Post - Depth First Search क्या है ? | DFS Example | DFS full Form in data structure पूरी तरह से समज में आया होगा और हमें यकीन है की आपको इस Article को पढ़कर काफी जानकारी भी मिली होगी.
यदि आपको हमारा यह लेख Depth First Search क्या है ? | DFS Example | DFS full Form in data structure पसंद आया है तो आप इसे अपने दोस्तों और अपने सोशल मीडिया पर शेयर जरुर करे. जिससे वह लोग भी इस जानकारी का फायदा उठा सके और यह जान सके.
अगर आप DFS जैसे ओर Topic के बारेमे जानना चाहते है तो Notification Allow जरूर करदे। ताकि ऐसी Information आपको Daily मिलती रहे।
Also Read This
Encryption kya hai? Meaning of encryption ?