Breadth-first search(BFS) क्या हैं:-
Breadth-First Search (BFS) एक ऐसी Technique जिसमे Level Wise Searching की जाती हैं।
इसमें level wise Means यह हैं कि जिस Node से Searching Start की जाती हैं उस Node के पास के सभी side वाले Nodes को travel किया जाता हैं उसके बाद ही Next Level को Travel किया जाता हैं।
इस तरह किसी Problem को search करना ही Breadth-First Search(BFS) कहलाता हैं।
यह Depth-First search(DFS) से Better Result Provide करती हैं।
इसे निचे लिखे कुछ Point से समझने की कोशिस करते हैं:-
Uninformed Search Technique:-
हम इसे Blind search Technique भी कहते हैं क्योकि इसमें हमे Next Node तक जाने में लगने वाली Cost का पता नहीं होता हैं।
2. Queue (FIFO):-
इसमें किसी Problem को Search करने के लिए Queue का use किया जाता हैं मतलब इसमें First in First out (FIFO) का use किया जाता हैं मतलब जो element पहले insert किया जाता हैं उसे पहले निकला जाता हैं।
3. Completeness:-
Completeness का यह हैं कि क्या यह हमे Definitely Answer देता हैं या नहीं, तो इसका answer हैं हा, क्योकि इसमें हम कोई भी Node बिना Travel किये आगे नहीं बढ़ते हैं।
इसमें यदि हमे Goal Node मिल जाती हैं तो हम उसके। …… के throw उसके Root aliment तक पहुंचते हैं तथा उसका path ऐसा होता हैं
माना कि F हमारी Goal State हैं तो इसका path ये होंगा:-
4. Shallowest Node:-
इसमें हम Level wise किसी भी problem का solution खोजते हैं या हम कह सकते हैं पहले हम जिस नोड को select करते हैं उसके side वाले सभी Node को travel किया जाता हैं और उसके बाद ही निचे वाले Node को travel करते हैं।
5. Optimal:-
यह हमेशा Optimal solution ही देंगा, क्योकि यदि हम सभी Edges की cost अलग अलग भी देते हैं फिर भी यह हमे Optimal solution ही देंगा, क्योकि इसमें searching Level wise होती हैं।
6. Time Complexity:-
इसकी time Complexity Depth First Search(DFS) से कम होती हैं।
O(bd)
