विस्तार-प्रधान खोज

विस्तार-प्रधान खोज (साँचा:lang-en या बीएफएस) ट्री या ग्राफ डेटा संरचनाओं की खोज या खोज के लिए एक कलन विधि है। यह ट्री के जड़(root) (या ग्राफ़ के कुछ मनमाने नोड,जिसे कभी-कभी 'खोज कुंजी' के रूप में संदर्भित किया जाता है) पर शुरू होता है और अगली गहराई पर नोड्स में जाने से पहले वर्तमान गहराई पर सभी पड़ोसी नोड्स की पड़ताल करता है।

यह गहराई-प्रधान खोज,जो सबसे पहले गहराई पर मौजूद नोड्स की पड़ताल करता है, से उलट है।

बीएफएस और रेखांकन के जुड़े घटकों को खोजने में इसके आवेदन का आविष्कार 1945 में कोनराड ज़्यूस द्वारा,उनके (अस्वीकृत) पीएच.डी. प्लैंकल्कल प्रोग्रामिंग भाषा पर थीसिस में किया गया था, लेकिन यह 1972 तक प्रकाशित नहीं हुई थी। इसे 1959 में एडवर्ड एफमूर द्वारा पुन: स्थापित किया गया था, जिन्होंने इसका उपयोग एक भूलभुलैया से बाहर सबसे छोटा रास्ता खोजने के लिए किया था, और बाद में सी.वाई. ली द्वारा एक वायर रूटिंग एल्गोरिथ्म (1961 में प्रकाशित) में विकसित किया गया।

छद्म कोड

निवेश(Input): एक ग्राफ G और एक प्रारंभिक नोड R जो G की जड़(root) नोड है।

उपज(Output):लक्ष्य अवस्था। जनक(parent) लिंक R तक जाने वाले सबसे छोटे मार्ग का पता लगाता है।

1  procedure BFS(G, root) is
2      let Q be a queue
3      label root as discovered
4      Q.enqueue(root)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered then
11                 label w as discovered
12                 w.parent := v
13                 Q.enqueue(w)

अधिक जानकारी

यह गैर-पुनरावर्ती(non-recursive) कार्यान्वयन गहराई-प्रधान खोज के गैर-पुनरावर्ती कार्यान्वयन के समान है, लेकिन दो तरीकों से इसमें भिन्नता है:

1. यह एक स्टैक के बजाय एक कतार(queue) (फर्स्ट इन फर्स्ट आउट) का उपयोग करता है।
2. यह जाँचता है कि क्या नोड कतारबद्ध करने से पहले खोजी जा चुकी है,बजाए की इस जांच को नोड को कतार से हटाते समय करने के।

यदि G एक ट्री है, विस्तार-प्रधान खोज की कलन विधि में कतार को स्टैक में बदलने से गहराई-प्रधान खोज कलन विधि प्राप्त होती है। सामान्य ग्राफ के लिए गहराई-प्रधान खोज की पुनरावृत्ति कार्यान्वयन में स्टैक को कतार से बदलने पर विस्तार-प्रधान खोज कलन विधि प्राप्त होती है,परन्तु सामान्य से भिन्न।

कतार Q उन नोड्स को रखता है जिनमे अभी खोज हो रही है।

कार्यान्वयन के आधार पर,नोड्स को जांचा हुआ(discovered) चिन्हित करने के लिए उन्हें एक सेट में संगृहीत किया जा सकता है अथवा इस जानकारी को नोड में के ही एक गुण(attribute) के तौर पर रखा जा सकता है।

प्रत्ये नोड का 'मूल'(parent) गुण नोड्स तक जाने वाले सबसे छोटे मार्ग को जानने के लिए इस्तेमाल किया जाता है। विस्तार-प्रधान खोज को चलने से विस्तार-प्रधान ट्री(Breadth-first Tree) का निर्माण होता है,जिसे नीचे दिए उदहारण में देखा जा सकता है।

उदहारण

निम्नलिखित फ्रैंकफर्ट से शुरू होने वाले जर्मन शहरों पर बीएफएस चलाकर प्राप्त किए गए विस्तार-प्रधान ट्री का एक उदाहरण है:

जर्मनी का एक नक्शा (एक ग्राफ़ के रूप में दिया गया) जो कई ग्राफ़ खोज एल्गोरिदम के लिए उदाहरण के लिए आधार के रूप में काम कर सकता है।

जर्मनी का एक नक्शा (एक ग्राफ़ के रूप में दिया गया) जो कई ग्राफ़ खोज कलन विधियों के लिए उदाहरण के लिए आधार के रूप में काम कर सकता है।

दिए गए नक्शे पर बीएफएस चलाने और फ्रैंकफर्ट में शुरू होने पर मिला विस्तार-प्रधान ट्री

विश्लेषण

सामयिक जटिलता एवं स्थान जटिलता (Time Complexity and Space Complexity)

सामयिक जटिलता को O(|V|+|E|) के रूप में दर्शाया जा सकता है ,जहाँ V सिरों(Vertex/Nodes) की संख्या सामयिक जटिलता E किनारों(Edges) की संख्या है। ऐसा इसलिए क्यूंकि निकृष्टतम समय में खोज हर सिरे एवं किनारे की जांच करेगी।

जब ग्राफ में सिरों की संख्या समय से पहले पता हो ,और अतिरिक्त डेटा संरचनाओं का उपयोग यह निर्धारित करने के लिए किया गया हो कि कतार में कौन से सिरे पहले से ही जोड़े गए हैं, तब स्थान जटिलता O(|V|) के रूप में व्यक्त की जा सकती है। यह ग्राफ़ के लिए आवश्यक स्थान के अतिरिक्त है, जो कि कलन विधि के कार्यान्वयन द्वारा उपयोग किए गए ग्राफ़ प्रतिनिधित्व के आधार पर भिन्न हो सकता है।

संपूर्णता

कलन विधियों के विश्लेषण में, विस्तार-प्रधान खोज के इनपुट को एक परिमित(finite) ग्राफ माना जाता है, जिसे स्पष्ट रूप से एक आसन्न सूची(Adjacency list), आसन्न मैट्रिक्स(Adjacency Matrix), या इसी तरह के प्रतिनिधित्व के रूप में दर्शाया गया हो। हालांकि, आर्टिफिशियल इंटेलिजेंस में ग्राफ ट्रावर्सल विधियों के अनुप्रयोग में इनपुट एक अनंत ग्राफ का निहित प्रतिनिधित्व हो सकता है। इस संदर्भ में, एक खोज विधि को पूर्ण होने के रूप में वर्णित किया जाता है यदि वह लक्ष्य अवस्था के मौजूद होने पर उसको ढूंढ़ने की गारंटी देती है। विस्तार-प्रधान खोज पूर्ण है, लेकिन गहराई-प्रधान खोज नहीं। जब स्पष्ट रूप से प्रतिनिधित्व किए गए अनंत ग्राफ पर लागू किया जाता है, तो विस्तार-प्रधान खोज में अंततः लक्ष्य स्थिति मिल जाएगी, लेकिन गहराई-प्रधान खोज ग्राफ़ के उन हिस्सों में खो सकती है, जिनके पास कोई लक्ष्य स्थिति नहीं है।

उपयोग

उदाहरण के लिए, ग्राफ थ्योरी में कई समस्याओं को हल करने के लिए विस्तार-प्रधान खोज का उपयोग किया जा सकता है:

• दो नोड्स u और v के बीच सबसे छोटा रास्ता खोजना, किनारों की संख्या द्वारा मापी गई लंबाई के साथ (गहराई-प्रधान खोज से बेहतर)
• (रिवर्स) कटहिल-मैकी मैश नंबरिंग
• एक फ्लो नेटवर्क में अधिकतम फ्लो की गणना के लिए फोर्ड-फुलकर्सन विधि
• ग्राफ में बाईपारटाइट गुण की जांच करना