Analisi della Depth First Search¶

Il tempo di esecuzione della DFS è il seguente. I cicli in dfs vengono eseguiti in \(O(V)\), non contando cosa avviene in dfsvisit, dal momento che sono eseguiti una sola volta per ogni vertice del grafo. In dfsvisit il ciclo è eseguito una per ogni arco nella lista di adiacenza del vertice corrente. Dal momento che dfsvisit è chiamata solamente se il vertice è bianco, il ciclo verrà eseguito una volta al massimo per ogni arco nel grafo, ovvero \(O(E)\). Per cui, il tempo totale è \(O(V + E)\).