La complexité de l'algorithme de parcours en largeur (BFS, Breadth-First Search) sur un graphe représenté par des listes d'adjacence est la suivante :

Complexité temporelle (temps d'exécution)
Cas général : 
𝑂
(
𝑉
+
𝐸
)
O(V+E)

𝑉
V = nombre de sommets (vertices).

𝐸
E = nombre d'arêtes (edges).
Chaque sommet est visité une fois (
𝑂
(
𝑉
)
O(V)), et chaque arête est explorée une fois (
𝑂
(
𝐸
)
O(E)).

Complexité spatiale (mémoire)
Cas général : 
𝑂
(
𝑉
)
O(V)
La mémoire est dominée par la file d'attente (queue) qui stocke les sommets à visiter, et par le tableau des sommets marqués comme visités.

Explications détaillées

Représentation par listes d'adjacence :

Chaque sommet a une liste de ses voisins.
Le coût pour parcourir tous les voisins d'un sommet 
𝑢
u est proportionnel au degré de 
𝑢
u, noté 
𝑑
(
𝑢
)
d(u).
La somme des degrés de tous les sommets est 
2
𝐸
2E (car chaque arête est comptée deux fois, une fois pour chaque sommet qu'elle relie).

Parcours BFS :

Initialisation : 
𝑂
(
𝑉
)
O(V) pour marquer tous les sommets comme non visités.
Pour chaque sommet 
𝑢
u visité, on parcourt ses voisins : 
𝑂
(
∑
𝑢
∈
𝑉
𝑑
(
𝑢
)
)
=
𝑂
(
2
𝐸
)
=
𝑂
(
𝐸
)
O(∑
u∈V
	​

d(u))=O(2E)=O(E).
Total : 
𝑂
(
𝑉
+
𝐸
)
O(V+E).

Cas particuliers :

Si le graphe est connexe, la complexité reste 
𝑂
(
𝑉
+
𝐸
)
O(V+E).
Si le graphe est non connexe, le BFS est exécuté pour chaque composante connexe, mais la complexité globale reste 
𝑂
(
𝑉
+
𝐸
)
O(V+E).

Comparaison avec une matrice d'adjacence
Avec une matrice d'adjacence, la complexité temporelle du BFS devient 
𝑂
(
𝑉
2
)
O(V
2
), car il faut parcourir toute la ligne de la matrice pour trouver les voisins de chaque sommet, même si le graphe est creux.

Conclusion
Pour un graphe représenté par des listes d'adjacence, le BFS est optimal avec une complexité de 
𝑂
(
𝑉
+
𝐸
)
O(V+E). C'est la représentation la plus efficace pour les graphes creux (
𝐸
≪
𝑉
2
E≪V
2
).