Quelle est la complexité de l'ampleur de la recherche d'un graphe complet?

Question

La complexité de BFS est dite linéaire, c'est-à-dire, O (V + E) mais le nombre total d'arêtes dans un graphe orienté complet est V * (V-1) qui est une fonction de degré 2 de la taille du graphique. Donc, le BFS prendrait-il le temps O (V^2) pour traverser un graphe complet?

Answer 1

Oui, je suppose que vous avez déjà fait le calcul.

O(V+E) = O(V + V*(V-1)) 
     = O(V + V*V - V) 
     = O(V*V) 

Answer 2

BFS s'exécute en O(V + E) à condition que le graphique soit représenté par la structure de liste d'adjacence. Dans le cas dense également, vous verrez la réponse sera O(V+E). (La représentation est une liste d'adjacence).

Dans le cas de la matrice d'adjacence O(V^2).

Peu importe la façon dont le graphique est, vous couvrez toujours le voisin du point de départ. Puis répétez cela pour les voisins aussi. Donc, vous pouvez voir qu'il devra toujours traverser en O(V+E) temps mais c'est la représentation qui le rend difficile pour la matrice d'adjacence. Ce sera donc O(V^2) .

_{C'est parce que chaque fois que nous voulons trouver quels sont les bords adjacents à un sommet donné « u », on traverse tout l'éventail adjmatrix[u], qui est de longueur | V |}