Pourquoi le tri topologique des DAG a-t-il une complexité temporelle de O(V+E) et pas seulement de O(V) ?

Question

https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search

La solution DFS à ce problème a une complexité en temps O(V+E). Mais pourquoi n'est-elle pas simplement O(V) ? Oui, nous visitons chaque sommet et chaque arête, mais chaque arête mène simplement à un autre sommet, ce n'est pas une étape supplémentaire. Par exemple, si nous avons 2 sommets, avec une arête entre eux, alors nous visitons 2 sommets, point. Nous ne visitons pas 3 choses (2 sommets + arête). Donnez-moi un exemple de DAG où 'V+E' donne lieu à plus de visites que 'V' seulement.

Pour renforcer mon argument, la complexité temporelle d'un DFS sur un arbre binaire est O(N), où N est le nombre de nœuds. Personne ne dit que c'est O(N+E).

Answer 1

Considérons un graphe orienté avec V sommets, divisé en deux groupes de taille V /2, avec une arête allant de chaque sommet du groupe #1 à chaque sommet du groupe #2. Il y a donc V 2 /4 arêtes, et vous devez les examiner toutes.