Python में डेप्थ-फर्स्ट सर्च: ग्राफ़ और ट्री का ट्रैवर्सल

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

यदि आप डेटा स्ट्रक्चर्स, एल्गोरिद्म, और समस्या-समाधान में रुचि रखते हैं, तो DataCamp आपके लिए है: अलग-अलग डेटा स्ट्रक्चर्स और उन्हें एक्सप्लोर करने के लिए बेहतरीन एल्गोरिद्म के बारे में अधिक जानें Data Structures and Algorithms in Python कोर्स और हमारे Data Structures: A Comprehensive Guide With Python Examples ट्यूटोरियल में।

डेप्थ-फर्स्ट सर्च क्या है?

डेप्थ-फर्स्ट सर्च (DFS) एक एल्गोरिद्म है जिसका उपयोग किसी डेटा स्ट्रक्चर, जैसे ग्राफ़ या ट्री, को ट्रैवर्स या सर्च करने के लिए किया जाता है। DFS के पीछे का मूल विचार यह है कि यह ग्राफ़ या ट्री की किसी शाखा में जितना संभव हो उतना नीचे तक जाता है और फिर वैकल्पिक शाखाओं का अन्वेषण करने के लिए बैकट्रैक करता है। यह अप्रोच ब्रेड्थ-फर्स्ट सर्च के विपरीत है, जो अगले स्तर पर जाने से पहले वर्तमान गहराई के सभी नोड्स को एक्सप्लोर करता है। आप ब्रेड्थ-फर्स्ट सर्च के बारे में HERE पढ़ सकते हैं।

DFS को एक भूलभुलैया के अन्वेषण की तरह समझें: आप एक रास्ता चुनते हैं और तब तक चलते हैं जब तक बंद गली न मिल जाए। जैसे ही उस रास्ते का अंत आता है, आप पिछली निर्णय-स्थल पर लौटते हैं और दूसरा मार्ग आज़माते हैं। यह गहरी पड़ताल DFS को तब बेहतरीन विकल्प बनाती है जब लक्ष्य किसी स्ट्रक्चर की पूरी तरह से जाँच करना हो, खासकर जब उसमें संभावित रास्तों की संख्या अधिक हो।

DFS विशेष रूप से उन समस्याओं में उपयोगी है जहाँ आपको हर संभव समाधान का अन्वेषण करना होता है।

इसके कुछ उदाहरण:

• AI में निर्णय ट्री नेविगेट करना, जहाँ हर शाखा विकल्पों के क्रम का प्रतिनिधित्व करती है और लक्ष्य सभी संभावित परिणामों का मूल्यांकन करना होता है।
• पाथफाइंडिंग समस्याएँ, जैसे गेम बोर्ड नेविगेशन या मानचित्र पर मार्ग ढूँढना, जिनमें विस्तृत सर्च की आवश्यकता होती है।

DFS यह सुनिश्चित करता है कि हर नोड एक बार विज़िट हो और एल्गोरिद्म पूरे ग्राफ़ या ट्री को कवर करे।

Python में डेप्थ-फर्स्ट सर्च की प्रमुख विशेषताएँ

डेप्थ-फर्स्ट सर्च में नोड्स को व्यवस्थित रूप से एक्सप्लोर करने और केवल आवश्यकता होने पर बैकट्रैक करने का तरीका होता है। आइए इसकी कुछ प्रमुख विशेषताओं पर नज़र डालें।

रिकर्सिव प्रकृति

मूल रूप से, DFS रिकर्सिव तरीके से काम करता है, यानी यह समस्या को हल करने के लिए खुद को बार-बार कॉल करता है, जैसे-जैसे वह स्ट्रक्चर में गहराई तक जाता है। जब DFS किसी शाखा में उतरता है, तो वह जितना संभव हो उतना गहराई तक उसे एक्सप्लोर करता है और फिर दूसरी शाखाओं को एक्सप्लोर करने के लिए ऊपर लौटता है। किसी पथ में गहराई तक जाना और आगे विकल्प न होने पर बैकट्रैक करना—इस प्रक्रिया को रिकर्शन से आदर्श रूप से संभाला जा सकता है। विस्तार से समझने के लिए देखें Understanding Recursive Functions in Python।

बैकट्रैकिंग

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

साइकल्स को संभालना

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

व्यापक अन्वेषण

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

Python में डेप्थ-फर्स्ट सर्च लागू करना

Python में डेप्थ-फर्स्ट सर्च लागू करने के दो मुख्य तरीके हैं: रिकर्सिव और इटरेटिव। प्रत्येक अप्रोच के अपने फायदे और समझौते हैं, और चुनाव अक्सर ग्राफ़ के आकार और आपकी समस्या पर निर्भर करता है।

दोनों तरीकों को दर्शाने के लिए, आइए एक सरल निर्णय ट्री बनाते हैं और उसे ट्रैवर्स करने के लिए DFS का उपयोग करते हैं। हम अपने उदाहरण के लिए Python का उपयोग करेंगे। आप हमेशा अपनी Python स्किल्स को ताज़ा करने के लिए Python Programming स्किल ट्रैक देख सकते हैं।

उदाहरण के तौर पर एक बाइनरी निर्णय ट्री लेते हैं। यहाँ एक सरल ट्री स्ट्रक्चर है जिसमें प्रत्येक नोड की दो चाइल्ड शाखाएँ हैं:

आइए इस निर्णय ट्री को Python में एक डिक्शनरी के रूप में स्पष्ट रूप से परिभाषित करें।

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}संचालित द्वारा

रिकर्सिव DFS

DFS प्रायः रिकर्सिव रूप से लागू किया जाता है। हर नोड पर, DFS अपने चाइल्ड नोड्स पर खुद को कॉल करता है जब तक विज़िट करने के लिए और नोड न बचें, और फिर बैकट्रैक करता है। यहाँ ट्री को ट्रैवर्स करने के लिए एक रिकर्सिव DFS फ़ंक्शन है।

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')संचालित द्वारा

इस रिकर्सिव संस्करण में, हम रूट नोड A से शुरू करते हैं और बैकट्रैक करने से पहले प्रत्येक शाखा में नीचे तक एक्सप्लोर करते हैं ताकि विकल्पों का अन्वेषण किया जा सके। यदि हम यह कोड चलाएँ, तो यह उस पथ का आउटपुट देगा जिसका अनुसरण करते हुए इस ट्री को एक्सप्लोर किया गया:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
Oसंचालित द्वारा

इटरेटिव DFS

बहुत बड़े निर्णय ट्री के लिए, Python की रिकर्शन डेप्थ लिमिट समस्या पैदा कर सकती है। ऐसे मामलों में, हम DFS को इटरेटिव रूप में लागू कर सकते हैं, जहाँ विज़िट किए जाने वाले नोड्स को मैनेज करने के लिए स्टैक का उपयोग होगा। उसी निर्णय ट्री के लिए इटरेटिव DFS इस प्रकार लागू किया जा सकता है:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')संचालित द्वारा

यह इटरेटिव अप्रोच स्टैक को मैन्युअली संभालकर रिकर्शन डेप्थ सीमाओं से बचता है, जो बड़े ट्री या गहरे स्ट्रक्चर्स के लिए उपयोगी हो सकता है। इस कोड को चलाने पर ऊपर जैसा ही आउटपुट मिलता है।

रिकर्सिव बनाम इटरेटिव DFS कब उपयोग करें

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

रिकर्सिव DFS

मैं सामान्यतः रिकर्सिव DFS की सरलता और सौंदर्य को प्राथमिकता देता/देती हूँ। यह अप्रोच सहज और साफ-सुथरी है।

फायदे:

• सरलता: कोड संक्षिप्त है और समस्या का अच्छा प्रतिबिंब है।
• पठनीयता: समझने में आसान, खासकर छोटे से मध्यम आकार की समस्याओं के लिए।

कमियाँ:

• रिकर्शन डेप्थ लिमिट: बड़े ग्राफ़्स के लिए आप Python की रिकर्शन डेप्थ लिमिट से टकरा सकते हैं।

रिकर्शन उन समस्याओं के लिए आदर्श है जहाँ ट्री या ग्राफ़ अपेक्षाकृत छोटा हो और Python की रिकर्शन डेप्थ के भीतर आसानी से आ जाए।

इटरेटिव DFS

लिखने में थोड़ा जटिल होने के बावजूद, इटरेटिव DFS अधिक लचीला है और रिकर्शन लिमिट की चिंता किए बिना बड़ी समस्याओं को संभाल सकता है। Python के कॉल स्टैक पर निर्भर होने के बजाय, इटरेटिव DFS स्पष्ट रूप से स्टैक के माध्यम से एक्सप्लोर किए जाने वाले नोड्स को मैनेज करता है।

फायदे:

• कोई रिकर्शन लिमिट नहीं: स्टैक को मैन्युअली मैनेज करने से Python की रिकर्शन डेप्थ लिमिट से बचाव होता है।

कमियाँ:

• ज़्यादा कोड: इटरेटिव DFS में अधिक सेटअप चाहिए और यह कम सहज हो सकता है।
• पठनीयता: कोड अक्सर थोड़ा अधिक विस्तृत होता है, जिससे उसे फॉलो करना कठिन हो सकता है।

इटरेटिव अप्रोच बड़े या जटिल समस्याओं के लिए सर्वोत्तम है जहाँ रिकर्शन डेप्थ चिंता का विषय हो। यह तब भी उपयोगी है जब आपको ट्रैवर्सल पर अधिक नियंत्रण चाहिए।

टाइम और स्पेस कॉम्प्लेक्सिटी

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

हम जटिलता पर चर्चा करने के लिए BigO नोटेशन का उपयोग करते हैं। Big O नोटेशन के ताज़ा ज्ञान के लिए देखें Big O Notation and Time Complexity Guide: Intuition and Math।

टाइम कॉम्प्लेक्सिटी

DFS की टाइम कॉम्प्लेक्सिटी O(V + E) होती है, जहाँ V नोड्स की संख्या है और E कनेक्शंस (जिन्हें "एजेस" कहते हैं) की संख्या है। DFS हर नोड और हर कनेक्शन को एक बार विज़िट करता है। इसलिए, DFS को लगने वाला कुल समय नोड्स और कनेक्शंस की संख्या पर निर्भर करता है।

स्पेस कॉम्प्लेक्सिटी

DFS में उपयोग की गई स्पेस इस पर निर्भर करती है कि किसी भी समय एल्गोरिद्म कितने नोड्स का ट्रैक रख रहा है। रिकर्सिव और इटरेटिव दोनों DFS नोड्स को ट्रैक करने के लिए स्टैक का उपयोग करते हैं। वर्स्ट-केस में, मेमोरी उपयोग पूरे ग्राफ़ के सभी नोड्स को समाहित कर सकता है, जिससे स्पेस कॉम्प्लेक्सिटी O(V) होती है।

एल्गोरिद्म की जटिलता मापने के अन्य तरीकों का अन्वेषण करें Analyzing Complexity of Code through Python ट्यूटोरियल में।

डेप्थ-फर्स्ट सर्च के वास्तविक जीवन के अनुप्रयोग

DFS कई क्षेत्रों में उपयोगी है, जिनमें कंप्यूटर विज्ञान, AI, और गेम डेवलपमेंट शामिल हैं। कुछ सामान्य अनुप्रयोगों के लिए नीचे दी गई तालिका देखें।

डेप्थ-फर्स्ट सर्च बनाम अन्य सर्च एल्गोरिद्म

आइए DFS की तुलना अन्य प्रसिद्ध एल्गोरिद्म जैसे ब्रेड्थ-फर्स्ट सर्च, Dijkstra’s एल्गोरिद्म और A* से करें।

डेप्थ-फर्स्ट सर्च बनाम ब्रेड्थ-फर्स्ट सर्च

ब्रेड्थ-फर्स्ट सर्च (BFS) ग्राफ़ को स्तर-दर-स्तर एक्सप्लोर करता है, वर्तमान गहराई के सभी नोड्स को विज़िट करने के बाद ही अगले स्तर पर जाता है। BFS विशेष रूप से तब उपयोगी है जब लक्ष्य किसी अनवेटेड ग्राफ़ में सबसे छोटा पथ खोजना हो। हालाँकि, BFS व्यापक ग्राफ़्स में बहुत मेमोरी उपयोग कर सकता है, क्योंकि उसे प्रत्येक स्तर के सभी नोड्स का ट्रैक रखना पड़ता है। BFS सोशल नेटवर्क विश्लेषण या सरल रूटिंग समस्याओं के लिए उत्कृष्ट विकल्प है।

दूसरी ओर, डेप्थ-फर्स्ट सर्च तब उपयोगी है जब लक्ष्य सभी संभावित पथों या समाधानों का अन्वेषण करना हो—जैसे पहेलियाँ सुलझाना या ग्राफ़ में साइकल्स खोजना। BFS के विपरीत, DFS सबसे छोटे पथ की गारंटी नहीं देता। लेकिन यह अधिक मेमोरी-कुशल है, क्योंकि इसे केवल वर्तमान पथ का ही ट्रैक रखना होता है।

आप ब्रेड्थ-फर्स्ट सर्च के बारे में और जान सकते हैं Breadth-First Search: A Beginner’s Guide with Python Examples में।

DFS बनाम Dijkstra का एल्गोरिद्म

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

डेप्थ-फर्स्ट सर्च एज वेट्स को ध्यान में नहीं रखता, इसलिए यह इष्टतम पथ की गारंटी नहीं देता। हालाँकि, अनवेटेड ग्राफ़्स में या जब एज वेट्स अप्रासंगिक हों, तब यह Dijkstra की तुलना में तेज़ हो सकता है।

आप Dijkstra’s एल्गोरिद्म के बारे में अधिक जान सकते हैं Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial में।

DFS बनाम A*

A* (उच्चारित “ए-स्टार”) एक एल्गोरिद्म है जो अपनी खोज को मार्गदर्शन देने के लिए एक ह्यूरिस्टिक शामिल करके Dijkstra में सुधार करता है। यह कई मामलों में इसे अधिक तेज़ और कुशल बनाता है। A* सबसे कम कॉस्ट वाले पथों (Dijkstra जैसा) की खोज और सीधे लक्ष्य की ओर बढ़ने के बीच संतुलन बनाता है, जैसे सीधे-रेखा दूरी जैसी ह्यूरिस्टिक का उपयोग करके। यह A* को GPS नेविगेशन या वीडियो गेम पाथफाइंडिंग जैसे कार्यों के लिए अत्यंत कुशल बनाता है।

डेप्थ-फर्स्ट सर्च कोई ह्यूरिस्टिक उपयोग नहीं करता, जिसका अर्थ है कि उसमें A* जैसी "दिशा" नहीं होती जो लक्ष्य तक कुशलतापूर्वक पहुँचने में मदद करे। DFS उन समस्याओं के लिए अधिक उपयुक्त है जहाँ पूरे ग्राफ़ या निर्णय ट्री का गहन सर्च चाहिए, जबकि A* तब बेहतर है जब किसी ह्यूरिस्टिक की मदद से सबसे छोटा पथ कुशलतापूर्वक खोजना हो।

आम गलतियाँ और उनसे कैसे बचें

डेप्थ-फर्स्ट सर्च का उपयोग करते समय, खासकर बड़े ग्राफ़्स में, कई सामान्य समस्याएँ सामने आ सकती हैं।

विज़िटेड नोड्स को ट्रैक न करना

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

रिकर्सिव DFS में स्टैक ओवरफ्लो

Python में रिकर्शन डेप्थ डिफ़ॉल्ट रूप से लगभग 1,000 स्तरों तक सीमित है, जिसका अर्थ है कि बड़े ग्राफ़्स में बहुत गहराई तक रिकर्सिव कॉल्स करने पर RecursionError हो सकता है। इसे रोकने के लिए, बड़े ग्राफ़्स के लिए इटरेटिव DFS का उपयोग करें। स्टैक को एक सूची के रूप में बनाए रखकर, हम रिकर्शन डेप्थ सीमाओं से बचते हैं और बहुत बड़े ग्राफ़्स को सुरक्षित रूप से हैंडल कर सकते हैं।

किसी समाधान को सबसे छोटा पथ समझ लेना

यह याद रखना भी महत्वपूर्ण है कि DFS दो नोड्स के बीच सबसे छोटे पथ की गारंटी नहीं देता। क्योंकि DFS पहले एक पथ को गहराई तक फॉलो करता है और फिर दूसरों को एक्सप्लोर करने के लिए बैकट्रैक करता है, यह कोई समाधान ढूँढ सकता है, लेकिन वह सबसे सीधा मार्ग नहीं भी हो सकता।

निष्कर्ष

डेप्थ-फर्स्ट सर्च ग्राफ़्स और ट्रीज़ को एक्सप्लोर और ट्रैवर्स करने के लिए एक शक्तिशाली एल्गोरिद्म है। पथों में गहराई तक उतरने और सभी संभावनाओं को एक्सप्लोर करने की इसकी क्षमता इसे भूलभुलैया सुलझाने, पहेलियाँ सुलझाने और निर्णय ट्री के अन्वेषण जैसी विविध समस्याओं के लिए उपयुक्त बनाती है।

यदि आप सर्च एल्गोरिद्म में रुचि रखते हैं, तो इस श्रृंखला के मेरे अन्य लेख देखें: Binary Search in Python: A Complete Guide for Efficient Searching और Breadth-First Search: A Beginner’s Guide with Python Examples। आपको यह भी रुचिकर लग सकता है: AVL Tree: Complete Guide With Python Implementation, और Introduction to Network Analysis in Python।