40. DFS vs. BFS : Choisir le Bon Parcours
Le DFS et le BFS ont la même complexité temporelle asymptotique, O(V + E) lors de l'utilisation d'une Liste d'Adjacence, mais ils résolvent mieux des problèmes différents.
| Caractéristique | DFS (Depth First Search) | BFS (Breadth First Search) |
|---|---|---|
| Structure de Données | Stack (Pile) (ou Récursivité) | Queue (File) |
| Modèle de Recherche | Profonde, épuisant un chemin d'abord | Large, explorant couche par couche |
| Complexité Temporelle | O(V + E) | O(V + E) |
| Complexité Spatiale | O(H) où H est la hauteur du graphe | O(B) où B est la largeur max/nombre de nœuds à un niveau |
| Meilleur pour | Détection de cycle, tri topologique, exploration de structures grandes et profondes (si la cible est probablement profonde). | Trouver les plus courts chemins (non pondérés), trouver des composants connectés, exploration peu profonde (si la cible est probablement proche du départ). |