BFS ਇੱਕ ਗ੍ਰਾਫ ਨੂੰ ਪੱਧਰ ਦਰ ਪੱਧਰ ਖੋਜਦਾ ਹੈ, ਇੱਕ ਨੋਡ ਦੇ ਸਾਰੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਗਹਿਰਾਈ ਵਿੱਚ ਜਾਣ ਤੋਂ ਪਹਿਲਾਂ ਵਿਜ਼ਿਟ ਕਰਦਾ ਹੈ। ਇਹ ਇੱਕ ਕਿਊ ਵਰਤਦਾ ਹੈ ਅਤੇ ਅਵਜ਼ਨ ਕੀਤੇ ਗ੍ਰਾਫ਼ਾਂ ਵਿੱਚ ਸਭ ਤੋਂ ਛੋਟਾ ਮਾਰਗ (ਘੱਟ ਤੋਂ ਘੱਟ ਕਿਨਾਰੇ) ਲੱਭਦਾ ਹੈ।
ਇੱਕ ਸਰੋਤ 'ਤੇ ਸ਼ੁਰੂ ਕਰੋ, ਇਸ ਨੂੰ ਕਿਊ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰੋ, ਫਿਰ ਬਾਰ-ਬਾਰ ਇੱਕ ਨੋਡ ਨੂੰ ਕਿਊ ਤੋਂ ਹਟਾਓ, ਇਸ ਦੇ ਅਵਿਜ਼ਿਟ ਗੁਆਂਢੀਆਂ ਨੂੰ ਵਿਜ਼ਿਟ ਕਰੋ, ਅਤੇ ਉਹਨਾਂ ਨੂੰ ਕਿਊ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰੋ। ਇੱਕ 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 ਛੋਟਤਮ ਪਾਥ ਲਈ ਐ ਐਲਗੋਰਿਦਮ ਹੈ ਜਦੋਂ ਹਰੇਕ ਕਿਨਾਰਾ ਬਰਾਬਰ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ — ਰਾਊਟਿੰਗ, ਵੈੱਬ ਕ੍ਰਾਲਿੰਗ, ਸੋਸ਼ਲ-ਨੈਟਵਰਕ ਵਿਖੋ ਤੋਂ ਆਲੀ।
ਇਸ ਦੀ ਕਿਊ-ਆਧਾਰਿਤ, ਪੱਧਰ-ਦਰ-ਪੱਧਰ ਸੰਰਚਨਾ ਇੱਕ ਬੁਨਿਆਦੀ ਟ੍ਰਾਵਰਸਲ ਪੈਟਰਨ ਹੈ।
BFS ਬਨਾਮ DFS ਜਾਣਨਾ ਤੁਹਾਨੂੰ ਪਹੁੰਚ ਯੋਗ ਤਾ, ਮਾਰਗ, ਅਤੇ ਆਰਡਰਿੰਗ ਸਮੱਸਿਆਵਾਂ ਲਈ ਸਹੀ ਸੰਦ ਚੁਣਨ ਦਿੰਦਾ ਹੈ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ