Pourquoi dire que la recherche en largeur se déroule dans le temps ?

Il est souvent indiqué (par exemple dans Wikipedia ) que le temps d'exécution de la recherche en largeur (BFS) sur un graphique est . Cependant, tout graphe connecté a | V | \ leq | E | +1 et, même dans un graphe non connecté, BFS ne regardera jamais un sommet en dehors du composant qui contient le sommet de départ. Ce composant contient au plus | E |  bords, donc il contient au plus | E | +1 sommets, et ce sont les seuls que l'algorithme visitera.$G=(V,E)$$O(|V|+|E|)$$|V|\leq |E|+1$$|E|$$|E|+1$

Cela signifie que $|V|+|E|\leq 2|E|+1$ , alors pourquoi ne dit-on pas que le temps d'exécution est simplement $O(|E|)$ ?

_{Cela est apparu dans les commentaires sur une question sur le temps d'exécution de l'algorithme de Disjkstra .}

BFS est généralement décrit quelque chose comme ce qui suit (de Wikipedia ).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

Le problème est quelque peu subtil: il se cache dans la ligne 3! La question est, quelle structure de données allons-nous utiliser pour stocker quels sommets ont été découverts?

La solution la plus simple consiste à utiliser un tableau booléen avec une entrée par sommet. Dans ce cas, nous devons initialiser chaque élément du tableau à falseet cela prend du temps . Cela s'applique à chaque graphique, même s'il n'y a aucun bord, donc nous ne pouvons supposer aucune relation entreet et nous obtenons un temps d'exécution de .$\Theta(|V|)$$|V|$$|E|$$O(|V|+|E|)$

Peut-on éviter d'avoir une structure de données avec un temps d'initialisation ? Notre première tentative pourrait être d'utiliser une liste chaînée. Cependant, maintenant tester si un sommet a été découvert (ligne 10) prend un temps linéaire dans le nombre de sommets visités, au lieu d'un temps constant comme auparavant. Cela signifie que le temps d'exécution devient , ce qui est bien pire dans le pire des cas. (Notez que nous ne voulons pas réécrire cela en car c'est encore pire: cela pourrait être aussi mauvais que , alors que )$\Theta(|V|)$$O(|V|\,|E|)$$O(|E|^2)$$|V|^4$$|V|\,|E|\leq |V|^3$

L'utilisation d'un tableau redimensionné dynamiquement nous permettrait de garder la liste triée, donc maintenant les recherches ne prendraient que le temps mais cela donne toujours un temps d'exécution de seulement , ce qui est encore pire que la norme.$O(\log|V|)$$O(|E|\log|V|)$

Enfin, nous pourrions utiliser une table de hachage de taille dynamique: commencer par une table de taille constante  et la doubler chaque fois qu'elle est à moitié pleine. Cela signifie que la taille finale de la table est au plus le double du nombre de sommets découverts avant la fin de l'algorithme, et c'est au plus car nous ne découvrons jamais rien en dehors de la composante du sommet de départ. De plus, la quantité totale de travail effectuée pour copier la table de hachage pour la développer est au maximum. Les recherches et les insertions dans la table de hachage sont amorties donc on obtient en effet un temps d'exécution de .$c$$|E|+1$$c + 2c + 4c + \dots + 2|E|\leq 4|E|$ $O(1)$$O(|E|)$

Donc est possible, mais voudrait le faire dans une vraie implémentation? Je dirais probablement que non. À moins que vous n'ayez des raisons de croire que vos graphiques en entrée auront de nombreux petits composants, la surcharge de maintenance de la table de hachage va ajouter un facteur constant notable au temps d'exécution. La croissance de la table de hachage pourrait prendre du tempset les recherches vous obligeront à calculer la fonction de hachage et, en moyenne, à regarder plus d'un emplacement dans le tableau. Les performances médiocres du cache des tables de hachage peuvent également vous blesser sur un véritable ordinateur. Dans la plupart des cas avec l'implémentation de tableau standard, la partie est le terme dominant du$O(|E|)$$4|E|$$O(|E|)$$O(|V|+|E|)$ le temps d'exécution, il n'est donc pas utile d'utiliser une table de hachage pour supprimer le terme dominé, étant donné le coût pratique de cette opération.