BFS con matrice di adiacenza

[peppe89ct]

Buongiorno secondo voi quale è la complessità di una breadth-first search eseguita con una matrice di adiacenza per un grafo orientato?
Io avrei pensato ad una [tex]O(E^2)[/tex] dove E è l'insieme degli archi...secondo voi??

[Danielking1]

ma il tempo per la visita è sempre lo stesso:

O(n + $ Sigma $ ( $ tau $ (v))

Ovvero i vari nodi vengono inseriti, esplorati e cancellati dalla coda al più una volta e questi richiede tempo O(n) più per ogni nodo devi vedere tutti i suoi archi incidenti e in una matrice di adiacenza che è di grandezza n per n questo richiede n quadro quindi in totale hai O(n + n quadro ) e quindi tempo totale O(n quadro) o se preferisci O(|V| quadro)...