Python में ब्रेड्थ-फर्स्ट सर्च: उदाहरणों के साथ मार्गदर्शिका

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

ब्रेड्थ-फर्स्ट सर्च डेटा साइंस में ग्राफ़ ट्रैवर्सल से लेकर पाथफाइंडिंग तक कई समस्याओं पर लागू होता है। यह अनवेटेड ग्राफ़ में सबसे छोटा पाथ खोजने के लिए खास तौर पर उपयोगी है। आगे पढ़ें—मैं ब्रेड्थ-फर्स्ट सर्च को विस्तार से समझाऊंगा और Python में इसका एक इम्प्लीमेंटेशन दिखाऊंगा। अगर शुरुआत में ही आपको Python में और मदद चाहिए, तो हमारा बेहद व्यापक Introduction to Python कोर्स जॉइन करें।

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

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

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

ब्रेड्थ-फर्स्ट सर्च एल्गोरिदम की प्रमुख विशेषताएँ

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

ट्रैवर्सल विधि

BFS वर्तमान गहराई स्तर के प्रत्येक नोड को, अगले स्तर पर जाने से पहले, एक्सप्लोर करता है। इसका मतलब है कि प्रारंभिक बिंदु से समान दूरी पर मौजूद सभी नोड्स को, गहराई में जाने से पहले, प्रोसेस किया जाता है।

क्यू-आधारित इम्प्लीमेंटेशन

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

अनवेटेड ग्राफ़ में सबसे छोटा पाथ सुनिश्चित

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

ग्राफ़ और ट्री—दोनों पर लागू

BFS ग्राफ़ और ट्री—दोनों पर काम करता है। ग्राफ़ जुड़े हुए नोड्स का नेटवर्क होता है जिसमें साइकल्स हो सकते हैं, जैसे सोशल नेटवर्क; जबकि ट्री एक पदानुक्रम होता है, जिसमें एक रूट और कोई साइकल नहीं होता, जैसे वंशावली। BFS दोनों के लिए उपयोगी है, जिससे यह कई तरह के कार्यों में व्यापक रूप से लागू हो जाता है।

Python में ब्रेड्थ-फर्स्ट सर्च इम्प्लीमेंट करना

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

चलिए शुरू करते हैं। पहले, हमें अपने BFS के लिए एक साधारण डिसीजन ट्री सेटअप करना होगा।

अब हम इस साधारण डिसीजन ट्री को Python डिक्शनरी से परिभाषित करेंगे, जहाँ प्रत्येक की एक नोड है, और उसका मान उस नोड के बच्चों की सूची है।

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],  # Node A connects to B and C
    'B': ['D', 'E'],  # Node B connects to D and E
    'C': ['F', 'G'],  # Node C connects to F and G
    'D': ['H', 'I'],  # Node D connects to H and I
    'E': ['J', 'K'],  # Node E connects to J and K
    'F': ['L', 'M'],  # Node F connects to L and M
    'G': ['N', 'O'],  # Node G connects to N and O
    'H': [], 'I': [], 'J': [], 'K': [],  # Leaf nodes have no children
    'L': [], 'M': [], 'N': [], 'O': []   # Leaf nodes have no children
}

अब Python में BFS एल्गोरिदम इम्प्लीमेंट करते हैं। BFS अगले स्तर पर जाने से पहले वर्तमान स्तर के सभी नोड्स को विज़िट करता है। हम यह तय करने के लिए कि अगला कौन-सा नोड विज़िट करना है, एक क्यू का उपयोग करेंगे।

from collections import deque  # Import deque for efficient queue operations

# Define the BFS function
def bfs(tree, start):
    visited = []  # List to keep track of visited nodes
    queue = deque([start])  # Initialize the queue with the starting node

    while queue:  # While there are still nodes to process
        node = queue.popleft()  # Dequeue a node from the front of the queue

        if node not in visited:  # Check if the node has been visited
            visited.append(node)  # Mark the node as visited
            print(node, end=" ")  # Output the visited node

            # Enqueue all unvisited neighbors (children) of the current node
            for neighbor in tree[node]:
                if neighbor not in visited:
                    queue.append(neighbor)  # Add unvisited neighbors to the queue

अब जब हमने अपना BFS फ़ंक्शन बना लिया है, तो हम इसे ट्री पर रूट नोड A से शुरू करते हुए चला सकते हैं।

# Execute BFS starting from node 'A'
bfs(tree, 'A')

इसे चलाने पर यह नोड्स को उसी क्रम में आउटपुट करता है जिसमें वे विज़िट हुए।

A B C D E F G H I J K L M N O

ट्री बनाम ग्राफ़ पर BFS

ट्री में BFS का ट्रैवर्सल पैटर्न सीधा-सादा होता है, क्योंकि वे स्वभावतः एसाइक्लिक होते हैं। एल्गोरिदम रूट से शुरू होता है और अगले स्तर पर जाने से पहले सभी बच्चों को विज़िट करता है। यह लेवल-ऑर्डर ट्रैवर्सल ट्री की पदानुक्रमिक संरचना का प्रतिबिंब है: प्रत्येक नोड का एक पैरेंट और अनेक बच्चे होते हैं, जिससे एक पूर्वानुमेय पैटर्न बनता है।

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

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

ब्रेड्थ-फर्स्ट सर्च कितनी कुशल है? हम Big O नोटेशन का उपयोग करके मूल्यांकन कर सकते हैं कि ग्राफ़ के आकार के साथ BFS की दक्षता कैसे बदलती है। 

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

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

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

BFS की स्पेस कॉम्प्लेक्सिटी O(V) है क्योंकि क्यू में नोड्स को स्टोर करने के लिए मेमोरी चाहिए। चौड़े ग्राफ़ में, एक समय में कई नोड्स स्टोर करने पड़ सकते हैं। सबसे खराब स्थिति में, संभव है कि एक साथ सभी नोड्स रखने पड़ें।

ब्रेड्थ-फर्स्ट सर्च के वास्तविक उपयोग

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

उपयोग के मामले

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

BFS पहेलियाँ हल करने में भी उपयोगी है, जैसे भूलभुलैया या स्लाइडर पज़ल्स। हर स्थिति एक नोड है, और कनेक्शन एजेज़ हैं। BFS स्टार्ट से एक्ज़िट तक का सबसे छोटा पाथ कुशलता से ढूंढ सकता है।

एक और शक्तिशाली उपयोग सोशल नेटवर्क विश्लेषण में है। BFS उपयोगकर्ताओं के बीच संबंध खोजने और प्रभावशाली नोड्स की पहचान करने में मदद करता है। यह सामाजिक कनेक्शनों का अन्वेषण कर संबंधित उपयोगकर्ताओं के क्लस्टर ढूंढ सकता है, जिससे नेटवर्क संरचनाओं पर अंतर्दृष्टि मिलती है।

AI में अनुप्रयोग

BFS AI प्रशिक्षण में भी उपयोगी है। उदाहरण के लिए, इसे शतरंज जैसे खेलों में गेम स्टेट्स सर्च करने के लिए इस्तेमाल किया जा सकता है। AI एल्गोरिदम संभावित चालों को लेवल दर लेवल एक्सप्लोर कर भविष्य की स्थितियों का आकलन करते हैं ताकि सर्वश्रेष्ठ कार्रवाई तय की जा सके, इस प्रकार विजय तक का सबसे छोटा पाथ खोजा जा सके।

BFS का उपयोग रोबोटिक्स में पाथ प्लानिंग के लिए भी किया जाता है। यह रोबोट्स को जटिल परिवेश में नेविगेट करने में सक्षम बनाता है—आसपास का मानचित्रण कर, बाधाओं से बचते हुए रास्ते खोजने में मदद करता है।

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

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

डेप्थ-फर्स्ट सर्च से तुलना

ब्रेड्थ-फर्स्ट सर्च और डेप्थ-फर्स्ट सर्च (DFS) दोनों ग्राफ़ ट्रैवर्सल एल्गोरिदम हैं, लेकिन वे अलग तरह से एक्सप्लोर करते हैं। BFS वर्तमान गहराई के सभी पड़ोसियों को विज़िट करता है, फिर गहराई में जाता है; जबकि DFS एक पाथ पर जितना संभव हो उतना नीचे जाता है और फिर बैकट्रैक करता है।

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

Dijkstra के एल्गोरिदम से तुलना

Dijkstra का एल्गोरिदम वेटेड ग्राफ़ के लिए बनाया गया ग्राफ़ ट्रैवर्सल एल्गोरिदम है, जहाँ एजेज़ की लागत अलग-अलग होती है। BFS के विपरीत, जो सभी एजेज़ को समान मानता है, Dijkstra एज वेट्स के आधार पर सबसे छोटा पाथ निकालता है। यह उन अनुप्रयोगों में सबसे उपयोगी है जहाँ लागत मायने रखती है, जैसे यात्रा समय को ध्यान में रखते हुए सर्वोत्तम रूट ढूँढना।

हालाँकि Dijkstra वेटेड ग्राफ़ के लिए शक्तिशाली है, यह अधिक जटिल और कम्प्यूटेशनली भारी होता है। प्रायोरिटी क्यूज़ का उपयोग करने पर Dijkstra का टाइम कॉम्प्लेक्सिटी O((V+E)log⁡V) होती है, जो BFS की O(V+E) टाइम कॉम्प्लेक्सिटी से काफ़ी अधिक है। आप Dijkstra के एल्गोरिदम के बारे में अधिक जान सकते हैं: Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial।

संभावित समस्याएँ

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

एक और सामान्य गलती क्यू का गलत उपयोग है। BFS इस क्यू पर निर्भर करता है कि किन नोड्स को एक्सप्लोर करना है। यदि क्यू को सही से मैनेज नहीं किया गया, तो ट्रैवर्सल में नोड्स छूट सकते हैं या पाथ गलत हो सकते हैं। इसे टालने के लिए, नोड्स को उसी क्रम में क्यू में जोड़ें जिसमें उन्हें एक्सप्लोर करना है और फिर निकालें। इससे BFS नोड्स को लेवल दर लेवल एक्सप्लोर करता है, जैसा कि इरादा है। Python में collections.deque जैसे भरोसेमंद डेटा स्ट्रक्चर का उपयोग मददगार होता है।

कब BFS का उपयोग न करें

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

निष्कर्ष

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

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