BFS ले ग्राफलाई स्तर दर स्तर अन्वेषण गर्छ, एक नोडको सबै छिमेकीहरू गहिराइमा जानु अघि भेट गर्छ। यसले queue प्रयोग गर्छ र अवजन गरिएको ग्राफहरूमा छोटतम पथ (सबैभन्दा कम किनारहरू) फेला पार्छ।
एक स्रोतमा सुरु गर्नुहोस्, यसलाई enqueue गर्नुहोस्, फिर एक नोडलाई बारम्बार dequeue गर्नुहोस्, यसको अनौठो छिमेकीहरू भेट गर्नुहोस्, र तिनलाई enqueue गर्नुहोस्। एक visited सेटले पुनः भेट गरेबाट रोक्छ।
from 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 प्रयोग गर्नुहोस्। यसले DFS भन्दा अधिक मेमोरी प्रयोग गर्छ (एकबारमा सम्पूर्ण सीमान्त)। visited ट्र्याक गर्नुहोस् नत्र तपाइँ चक्रहरूमा सधैंको लागि लुप हुन सक्नुहुन्छ।
BFS सबै किनारहरू समान रूपमा गणना गर्दा छोटतम पथको लागि को एल्गोरिदम हो — राउटिङ, वेब क्रलिङ, सामाजिक-नेटवर्क अलगावको डिग्रीहरू।
यसको queue-आधारित, स्तर-दर-स्तर संरचना एक मौलिक ट्रभर्सल प्याटर्न हो।
BFS बनाम DFS जान्दै तपाइँलाई पहुँच क्षमता, पथ, र अर्डरिङ समस्याहरूको लागि सही उपकरण चुन्न दिन्छ।