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