BFS utforsker en graf nivå for nivå, og besøker alle naboer til en node før det går dypere. Det bruker en kø og finner den korteste stien (færrest kanter) i uvektede grafer.
Ideen
Start ved en kilde, sett den inn i køen, fjern deretter gjentatte ganger en node fra køen, besøk dens ubesøkte naboer, og sett dem inn i køen. Et visited sett forhindrer gjenbesøk.
Eksempel
collections deque
():
visited = {start}
queue = deque([start])
order = []
queue:
node = queue.popleft()
order.append(node)
nbr graph[node]:
nbr visited:
visited.add(nbr)
queue.append(nbr)
order
graph = {: [, ], : [], : [], : []}
bfs(graph, )
