Complessità temporale e spaziale

Complessità temporale:

• O(V + E)
  • La creazione della lista di adiacenza visita ogni arco una volta e l'attraversamento visita ogni vertice e considera ogni arco un numero costante di volte.

Complessità spaziale:

• O(V + E)
  • La lista di adiacenza memorizza ogni arco, mentre l'array dei visitati e lo stack contengono ciascuno fino a V vertici.

Riepilogo:

• La DFS esplora prima in profondità e torna indietro quando non trova più vicini non visitati.
• Ha una complessità temporale lineare ed è alla base di molti algoritmi sui grafi.