Explication des temps d'exécution de BFS et DFS

Question

Pourquoi les temps d'exécution de BFS et DFS O(V+E), en particulier lorsqu'il y a un nœud qui a un bord dirigé vers un nœud qui peut être atteint depuis le sommet, comme dans cet exemple du site suivant

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Answer 1

Vous visitez chaque bord au plus deux fois. Il y a des bords E. Il y aura donc des opérations de visite de bord 2*E. Plus les nœuds ceux-ci n'ont pas d'arêtes ou en d'autres termes, de degré 0. Il peut y avoir au plus V de tels nœuds. Donc la complexité s'avère être, O(2*E + V) = O(E + V)