विस्तार-प्रधान खोज
From Wikipedia, the free encyclopedia
विस्तार-प्रधान खोज (अंग्रेज़ी: Breadth-first Search या बीएफएस) ट्री या ग्राफ डेटा संरचनाओं की खोज या खोज के लिए एक कलन विधि है। यह ट्री के जड़(root) (या ग्राफ़ के कुछ मनमाने नोड,जिसे कभी-कभी 'खोज कुंजी'[1] के रूप में संदर्भित किया जाता है) पर शुरू होता है और अगली गहराई पर नोड्स में जाने से पहले वर्तमान गहराई पर सभी पड़ोसी नोड्स की पड़ताल करता है।
यह गहराई-प्रधान खोज,जो सबसे पहले गहराई पर मौजूद नोड्स की पड़ताल करता है, से उलट है[2]।
बीएफएस और रेखांकन के जुड़े घटकों को खोजने में इसके आवेदन का आविष्कार 1945 में कोनराड ज़्यूस द्वारा,उनके (अस्वीकृत) पीएच.डी. प्लैंकल्कल प्रोग्रामिंग भाषा पर थीसिस में किया गया था, लेकिन यह 1972 तक प्रकाशित नहीं हुई थी[3]। इसे 1959 में एडवर्ड एफमूर द्वारा पुन: स्थापित किया गया था, जिन्होंने इसका उपयोग एक भूलभुलैया से बाहर सबसे छोटा रास्ता खोजने के लिए किया था[4][5], और बाद में सी.वाई. ली द्वारा एक वायर रूटिंग एल्गोरिथ्म (1961 में प्रकाशित) में विकसित किया गया[6]।