BFS किसी graph को level दर level explore करता है, और किसी node के सभी neighbors को visit करने के बाद ही गहराई में जाता है। यह एक queue का उपयोग करता है और unweighted graphs में shortest path (सबसे कम edges) खोजता है।
एक source से शुरू करें, उसे enqueue करें, फिर बार-बार किसी node को dequeue करें, उसके बिना-visited neighbors को visit करें, और उन्हें enqueue करें। एक set दोबारा visit करने से रोकता है।
visitedfrom collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
BFS का उपयोग unweighted graphs में shortest path, level-order traversal, और connected components खोजने के लिए करें। यह DFS की तुलना में अधिक memory का उपयोग करता है (एक ही बार में पूरा frontier)। हमेशा visited को track करें, वरना cycles पर आप हमेशा के लिए loop में फँस सकते हैं।
जब हर edge का समान महत्व हो, तब shortest paths के लिए BFS वही algorithm है — routing, web crawling, social-network में degrees of separation।
इसकी queue-आधारित, level-दर-level संरचना एक मौलिक traversal pattern है।
BFS बनाम DFS को जानना आपको reachability, paths, और ordering समस्याओं के लिए सही उपकरण चुनने देता है।
विस्तृत उत्तरों के साथ IT इंटरव्यू प्रश्नों की एक लाइब्रेरी — जूनियर से सीनियर तक।
दान करें