BFS ایک گراف کو سطح درجہ سطح سے تلاش کرتا ہے، کسی نوڈ کے تمام ہمسایوں کو گہرائی میں جانے سے پہلے دیکھتا ہے۔ یہ ایک queue استعمال کرتا ہے اور سب سے مختصر راستہ (سب سے کم edges) غیر وزنی گرافس میں تلاش کرتا ہے۔
ایک source سے شروع کریں، اسے enqueue کریں، پھر بار بار ایک نوڈ کو dequeue کریں، اس کے unvisited ہمسایوں کو دیکھیں، اور انہیں enqueue کریں۔ ایک visited set دوبارہ دیکھے جانے سے روکتا ہے۔
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 کو غیر وزنی گرافس میں سب سے مختصر راستے کے لیے، level-order traversal کے لیے، اور connected components تلاش کرنے کے لیے استعمال کریں۔ یہ DFS کے مقابلے میں زیادہ میموری استعمال کرتا ہے (ایک وقت میں پورا frontier)۔ ہمیشہ visited کو track کریں یا آپ cycles پر ہمیشہ کے لیے loop میں پھنس سکتے ہیں۔
BFS یہ algorithm ہے سب سے مختصر راستوں کے لیے جب ہر edge برابر اہم ہو — routing، web crawling، social-network degrees of separation۔
اس کی queue-based، level-by-level ساخت ایک بنیادی traversal pattern ہے۔
BFS بمقابلہ DFS کو جاننا آپ کو reachability، paths، اور ordering مسائل کے لیے صحیح tool منتخب کرنے دیتا ہے۔