डेटा संरचना - चौड़ाई पहले ट्रैवर्सल

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

जैसा कि ऊपर दिए गए उदाहरण में बताया गया है, बीएफएस एल्गोरिथ्म ए से बी से एफ तक पहले तो फिर सी और जी से डी तक जाता है। यह निम्नलिखित नियमों को नियोजित करता है।

  • Rule 1- समीपवर्ती अप्रकाशित कगार पर जाएँ। इसे चिह्नित के रूप में चिह्नित करें। इसे प्रदर्शित करें। इसे एक कतार में डालें।

  • Rule 2 - यदि कोई निकटवर्ती शीर्ष नहीं पाया जाता है, तो कतार से पहला शीर्ष हटा दें।

  • Rule 3 - जब तक कतार खाली न हो जाए तब तक नियम 1 और नियम 2 को दोहराएं।

चरण traversal विवरण
1
कतार को प्रारंभ करें।
2
हम जाने से शुरू करते हैं S (नोड शुरू), और इसे दौरा के रूप में चिह्नित करें।
3
हम तब से एक असंगत आसन्न नोड देखते हैं S। इस उदाहरण में, हमारे पास तीन नोड हैं लेकिन वर्णानुक्रम में हम चुनते हैंAके रूप में चिह्नित और इसे enqueue चिह्नित करें।
4
इसके बाद, से असमान आसन्न नोड S है B। हम इसे यात्रा के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।
5
इसके बाद, से असमान आसन्न नोड S है C। हम इसे यात्रा के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।
6
अभी, Sबिना किसी आसन्न नोड के साथ छोड़ दिया जाता है। तो, हम धोखा देते हैं और पाते हैंA
7
से A हमारे पास है Dअसमान आसन्न नोड के रूप में। हम इसे यात्रा के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।

इस स्तर पर, हमें बिना किसी चिन्हित (अप्रभावित) नोड्स के साथ छोड़ दिया जाता है। लेकिन एल्गोरिथ्म के अनुसार हम सभी गैर-प्रमाणित नोड्स प्राप्त करने के लिए छलावा करते रहते हैं। जब कतार खाली हो जाती है, तो कार्यक्रम समाप्त हो जाता है।

सी प्रोग्रामिंग भाषा में इस एल्गोरिथ्म के कार्यान्वयन को यहां देखा जा सकता है ।