Analisi della Breadth First Search¶

Prima che continuiamo con altri algoritmi, analizziamo il tempo dell’algoritmo. La prima cosa che possiamo osservare che il ciclo while loop viene eseguito al più una volta per ogni vertice nel grafo in \(|V|\). Possiamo vedere che questo è vero perchè un vertice deve essere bianco prima che venga esaminato e aggiunto alla coda. Questo ci dà \(O(V)\) per il ciclo while. Il ciclo for, che è annidato nel ciclo while è eseguito al più una volta per ogni arco nel grafo, in \(|E|\). La ragione è che ogni vertice è estratto dalla coda al più una volta e esaminiamo un arco dal nodo \(u\) al nodo \(v\) solamente quando il nodo \(u\) è estratto dalla coda. Questo ci dà \(O(E)\) per il ciclo. Combinando i due cicli otteniamo \(O(V + E)\).

Il costo dell’algoritmo per determinare il cammino all’indietro da un nodo qualsiasi alla radice in un albero di BFS è il seguente. Il caso peggiore è quando il grafo è una singola lunga catena di nodi. In questo caso attraversare la catena all’indietro ci costa \(O(V)\).