La BFS visita i nodi del grafo in ordine di distanza dalla sorgente della visita. Possiamo quindi costruire un array di distanze dove è la distanza minima dal nodo sorgente al nodo . Per convenzione possiamo imporre se non è raggiungibile da .
La complessità temporale è .
Algoritmo
def vettore_distanze_bfs(grafo, sorgente):
n = len(grafo)
distanze = [float('inf')]*n
distanze[sorgente] = 0
coda = [sorgente]
testa = 0
while testa < len(coda):
nodo_corrente = coda[testa]
testa += 1
for vicino in grafo[nodo_corrente]:
if grafo[vicino] == float('inf'):
distanze[vicino] = distanze[nodo_corrente] + 1
coda.append(vicino)