हेलो दोस्तों आज हम BFS के बारे में समझेंगे, यह क्या हैं, (BFS in Hindi) और कैसे काम करता है। BFS का full form है (Breadth first search) तो चलिए आसान शब्दों में BFS के बारे में समझते हैं।
सबसे पहले जान लीजिये की breadth first search (BFS) एक graph traversal techniques है, जिसका उपयोग किसी graph में vertices या Nodes का पता लगाने के लिए किया जाता है।
graph traversal technique :- यह एक प्रकार का process होता है, जिसमें ग्राफ पर मौजूद हर एक vertex/ node को visit किया जाता है, उसे check/Update किया जाता है, यानि इस टेक्निक द्वारा यह सुनिश्चित किया जाता है, की हाँ ग्राफ में मौजूद हर एक vertex थता Edge को चेक कर लिया गया है।
Vertices और Edge :- किसी भी Graph में दो चीजें मौजूद होती हैं, Points थता lines, तो ग्राफ में मौजूद Points को Vertices या Nodes कहाँ जाता है, और उन्हें आपस में जोड़ रही lines को Edge कहा जाता है।
What is BFS in Hindi | Breadth first search क्या है
BFS एक बहुत ही महत्वपूर्ण ग्राफ़ ट्रेवेर्सल अल्गोरिथम है, जिसका उपयोग किसी ग्राफ में मौजूद सबसे shortest path का पता लगाने के लिया किया जाता है। यह Queue data structure का उपयोग करता है, जो की (FIFO) first in first out method को फॉलो करता है। BFS का उपयोग GPS navigation system, Network analysis तथा विभिन्न games में किया जाता है।
यदि इस अल्गोरिथम की कार्यप्रणाली की बात करें तो, BFS अल्गोरिथम सबसे पहले किसी Graph में अपने single source point, starting node यानि किसी एक Random Node को select करता है, फिर उस Node से जुड़े हुवे दूसरे सभी Nodes को यह एक-एक कर visit करता है, और जिस-जिस node को यह visit करता है, उसे Mark करता जाता है, ताकि कोई भी Node छूटे नहीं या दुबारा visit ना हो सके।
आपको बता दें की BFS किसी Graph को Layer wise (Horizontally) चेक करता है। यह पहले किसी एक Random Node को select करता है, और फिर उसके (Adjacent node) यानि उसके Child node’s को visit करता है। इसी प्रकार यह प्रक्रिया तब तक चलती रहती है, जब तक की सभी Nodes तथा उनके Child nodes को सफलतापूर्वक visit और Mark नहीं किया जाता है।
चलिए उदाहरण द्वारा BFS की वर्किंग को समझते हैं, (BFS in hindi)
इस ग्राफ में A को हम source node के रूप में लेंगे, और find करेंगे की ग्राफ में H कहाँ पर मौजूद है। ग्राफ को देखने पर पता चलता है, की इसमें H मौजूद नहीं है, लेकिन BFS अल्गोरिथम इसे कैसे Identify करता है, चलिए जानते हैं। इसके लिए हम Queue को maintain करेंगे जो की Nodes के traversal order को सुनिश्चित करेगा।
Step 1 :- सबसे पहले हम Queue को Initialize करेंगे।
Queue
Step 2 :- अब A को starting node मानकर A से शुरुवात करेंगे और उसे visited mark करेंगे।
Queue
| A |
Step 3 :- अब A को dequeue करेंगे और dequeued node A को Key H के साथ compare करेंगे और match नहीं होने पर A के अगले Unexplored nodes को चेक करेंगे। A के नजदीकी Unvisited Nodes जो की B और C हैं, उनमे से क्रम अनुसार हम B को चुनेंगे और उसे visited मार्क कर Enqueue करेंगे। इसी प्रकार Node C को भी चेक किया जाएगा और queue में add कर visited मार्क कर दिया जाएगा।
Queue
| B | c |
Step 4 :- अब B को dequeue करेंगे और चेक करेंगे की क्या वह H Key से match करता है, या नहीं, तो यहाँ पर B Key से मैच नहीं करता है, तो B के सभी नजदीकी Unvisited nodes को enqueue करेंगे। B का नजदीकी unvisited node हैं, D और E तो उन्हें queue में ऐड करेंगे।
Queue
| C | D | E |
Step 5 :- अब यहाँ पर C को dequeue करेंगे और चेक करेंगे की क्या C key H से match करता है, या नहीं, वह मैच नहीं करता है, तो यहाँ पर C के सभी नजदीकी Unvisited नोड्स को queue में add कर देंगे।
Queue
| D | E | F | G |
Step 6 :- इसी प्रकार अब D को dequeue करेंगे और चेक करेंगे की क्या वह key H के साथ मैच करता है, या नहीं, तो वह मैच नहीं करता है। अब यहाँ पर D के सभी नजदीकी unvisited nodes को Enqueue किया जाएगा लेकिन यहाँ पर D के सभी नजदीकी nodes को विजिट कर लिया गया है, तो अब किसी भी नोड को Enqueue नहीं किया जाएगा।
Queue
| E | F | G |
step 7 :- अब E को dequeue किया जाएगा और चेक किया जाएगा की क्या वह Key H के साथ match करता है, तो यहाँ पर वह Key से मैच नहीं करता है। अब यहाँ पर E के सभी नजदीकी नोड्स को Queue में ऐड करेंगे, लेकिन E के सभी नजदीकी नोड्स को भी visit कर लिया गया है, तो कोई भी नोड ऐड नहीं होगा।
Queue
| F | G |
Step 8 :- इसी प्रकार अब नोड F को dequeue करेंगे और Key H के साथ उसे match किया जाएगा, और Key नहीं मिलने पर आगे की प्रक्रिया होगी जिसमे F के सभी नजदीकी Unvisited nodes को Queue में add किया जाएगा। यहाँ पर F के नजदीकी नोड visited और Marked है, तो Queue में कोई नया नोड ऐड नहीं होगा।
Queue
| G |
Step 9 :- इसी प्रकार नोड G को भी dequeue कर उसका Key H के साथ मैच किया जाएगा, जो की मैच नहीं करेगा। फिर G के नजदीकी unvisited नोड्स को queue में ऐड करेंगे, लेकिन यहाँ पर G के नजदीकी नोड को visit कर लिया गया है, तो Queue में कोई भी नया नोड ऐड नहीं होगा।
Queue
| Empty |
Step 10 :- तो हमने यहाँ पर सभी नोड्स को विजिट कर लिया है, और कोई भी नोड unvisited नहीं बचा है। इस से पता चलता है, की ग्राफ में H key मौजूद नहीं है। तो ऐसे Breadth first search (BFS) परत दर परत यानि layers में ग्राफ को चेक करता है।
आपने BFS अल्गोरिथम के बारे में पढ़ा (BFS In Hindi) उम्मीद है, आपको यह जानकारी ज्ञानवर्धक लगी होगी, यदि जानकारी अच्छी लगी है, तो इसे अपने दोस्तों के साथ भी शेयर करें।
यह भी पढ़ें :-