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