BFS గ్రాఫ్ను స్థాయిలో-స్థాయి ద్వారా అన్వేషిస్తుంది, నోడ్ యొక్క అన్ని పొరుగువారిని దర్శించిన తర్వాత లోతుకు వెళ్లటానికి ముందు. ఇది క్యూ ను ఉపయోగిస్తుంది మరియు అతి-చిన్న పాత (కనీస అంచులు) బరువులేని గ్రాఫ్లలో కనుగొంటుంది.
మూలం నుండి ప్రారంభించండి, దానిని క్యూలో నిక్షేపించండి, తర్వాత నోడ్ను పదేపదే ఎంపిక చేయండి, దాని సందర్శించని పొరుగువారిని సందర్శించండి మరియు వాటిని క్యూలో నిక్షేపించండి. సెట్ పునరాবృత్తి సందర్శనను నిరోధిస్తుంది.
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 ఉపయోగించండి. ఇది DFS కంటే ఎక్కువ మెమరీని ఉపయోగిస్తుంది (ఒక సరిహద్దు మొత్తం ఒక సమయంలో). ఎల్లప్పుడు visited ను ట్రాక్ చేయండి లేదా మీరు సైకిల్ల్ను నిరంతరం లూప్ చేయవచ్చు.
BFS అనేది అత్యంత-చిన్న పాత కోసం అల్గోరిదం, ప్రతి అంచు సమానంగా లెక్కించినప్పుడు — రూటింగ్, వెబ్ క్రాలింగ్, సామాజిక-నెట్వర్క్ విభజన డిగ్రీలు.
ఇది క్యూ-ఆధారిత, స్థాయిలో-స్థాయి రూపకల్పన ఒక ప్రాథమిక ట్రావర్సల్ నమూనా.
BFS బెర్ఫ్ DFS కు సంబంధించిన జ్ఞానం మిమ్మల్ని చేరుకోవటం, పాతలు, మరియు ఆర్డరింగ్ సమస్యల కోసం సరిగ్గా సాధనాన్ని ఎంపిక చేయడానికి అనుమతిస్తుంది.