Breadth First Search
BFS signifie Breadth First Search est une technique basée sur les sommets pour trouver le plus court chemin dans un graphe. Elle utilise une structure de données de type Queue qui suit le principe du premier entré, premier sorti. Dans BFS, un sommet est sélectionné à la fois lorsqu’il est visité et marqué, puis ses adjacents sont visités et stockés dans la file d’attente. Il est plus lent que DFS.
Ex-
A / \ B C / / \ D E F
La sortie est:
A, B, C, D, E, F
Depth First Search
DFS signifie Depth First Search est une technique basée sur les bords. Elle utilise la structure de données Stack, effectue deux étapes, d’abord les sommets visités sont poussés dans la pile et deuxièmement s’il n’y a pas de sommets alors les sommets visités sont poppés.
Ex-
A / \ B C / / \ D E F
Les résultats sont:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS |
|---|---|---|
| BFS signifie Breadth First Search. | DFS signifie Depth First Search. | |
| BFS(Breadth First Search) utilise la structure de données Queue pour trouver le plus court chemin. | DFS(Depth First Search) utilise la structure de données Stack. | |
| BFS peut être utilisé pour trouver le plus court chemin à source unique dans un graphe non pondéré, car dans BFS, nous atteignons un sommet avec un nombre minimum d’arêtes depuis un sommet source. | En DFS, nous pourrions traverser plus d’arêtes pour atteindre un sommet de destination à partir d’une source. | |
| BFS est plus approprié pour rechercher des sommets qui sont plus proches de la source donnée. | DFS est plus approprié quand il y a des solutions éloignées de la source. | |
| BFS considère tous les voisins en premier et ne convient donc pas aux arbres de décision utilisés dans les jeux ou les énigmes. | DFS est plus adapté aux problèmes de jeux ou de casse-tête. On prend une décision, puis on explore tous les chemins à travers cette décision. Et si cette décision conduit à une situation gagnante, on s’arrête. | La complexité temporelle de BFS est O(V + E) lorsque la liste d’adjacence est utilisée et O(V^2) lorsque la matrice d’adjacence est utilisée, où V représente les sommets et E les arêtes. | La complexité temporelle de DFS est également O(V + E) lorsque la liste d’adjacence est utilisée et O(V^2) lorsque la matrice d’adjacence est utilisée, où V représente les sommets et E représente les arêtes. |
Veuillez également voir BFS vs DFS pour l’arbre binaire pour les différences pour un Traversée d’arbre binaire.