BFS et DFS sont les méthodes de parcours utilisées pour rechercher un graphique. La traversée de graphe est le processus de visite de tous les nœuds du graphe. Un graphique est un groupe de sommets 'V' et de bords 'E' se connectant aux sommets.
Tableau de comparaison
| Base de comparaison | BFS | DFS |
|---|---|---|
| De base | Algorithme basé sur le sommet | Algorithme basé sur les bords |
| Structure de données utilisée pour stocker les nœuds | Queue | Empiler |
| Consommation de mémoire | Inefficace | Efficace |
| Structure de l'arbre construit | Large et court | Étroit et long |
| Mode traversante | Les plus anciens sommets non visités sont d'abord explorés. | Les sommets le long du bord sont explorés au début. |
| Optimalité | Optimal pour trouver la distance la plus courte, sans coût. | Pas optimal |
| Application | Examine le graphe bipartite, la composante connectée et le chemin le plus court présent dans un graphe. | Examine le graphe connecté à deux arêtes, le graphe fortement connecté, le graphe acyclique et l'ordre topologique. |
Définition de BFS
La largeur première recherche (BFS) est la méthode de déplacement utilisée dans les graphiques. Il utilise une file d'attente pour stocker les sommets visités. Dans cette méthode, l'accent est mis sur les sommets du graphique, un sommet est sélectionné en premier, puis il est visité et marqué. Les sommets adjacents au sommet visité sont ensuite visités et stockés de manière séquentielle dans la file d'attente. De même, les sommets stockés sont ensuite traités un par un et leurs sommets adjacents sont visités. Un nœud est entièrement exploré avant de se rendre dans un autre nœud du graphe, autrement dit, il traverse en premier les nœuds non explorés les moins profonds.
Exemple
Nous avons un graphe dont les sommets sont A, B, C, D, E, F, G. Considérant A comme point de départ. Les étapes du processus sont les suivantes:
- Le sommet A est développé et stocké dans la file d'attente.
- Les sommets B, D et G successeurs de A sont développés et stockés dans la file d'attente tandis que le sommet A est supprimé.
- Maintenant, B en tête de la file d'attente est supprimé et le stockage de ses sommets successeurs E et F.
- Le sommet D se trouvant au début de la file d'attente est supprimé et son nœud connecté F est déjà visité.
- Le sommet G est retiré de la file d'attente et son successeur E est déjà visité.
- Maintenant, E et F sont supprimés de la file d'attente et son sommet C successeur est traversé et stocké dans la file d'attente.
- Enfin, C est également supprimé et la file d'attente est vide, ce qui signifie que nous avons terminé.
- La sortie générée est - A, B, D, V, E, F, C.
BFS peut être utile pour déterminer si le graphique a des composants connectés ou non. Et aussi, il peut être utilisé pour détecter un graphe bipartite .
Un graphique est bipartite lorsque les sommets du graphique sont séparés en deux ensembles disjoints; il n'y aurait pas deux sommets adjacents dans le même ensemble. Une autre méthode de vérification d'un graphique bipartite consiste à vérifier l'occurrence d'un cycle impair dans le graphique. Un graphe bipartite ne doit pas contenir de cycle impair.
BFS est également plus apte à trouver le chemin le plus court du graphique pouvant être considéré comme un réseau.
Définition de DFS
La méthode de parcours DFS (Depth First Search) utilise la pile pour stocker les sommets visités. DFS est la méthode basée sur les arêtes et fonctionne de manière récursive, les sommets étant explorés le long d'un chemin (arête). L'exploration d'un nœud est suspendue dès qu'un autre nœud non exploré est trouvé et que les nœuds les plus profonds non explorés sont traversés au premier plan. DFS traverse / visite chaque sommet exactement une fois et chaque bord est inspecté exactement deux fois.
Exemple
Semblable à BFS, prenons le même graphique pour effectuer des opérations DFS, et les étapes impliquées sont les suivantes:
- Considérant A comme le sommet de départ qui est exploré et stocké dans la pile.
- Le sommet suivant de B est stocké dans la pile.
- Le sommet B a deux successeurs E et F, parmi lesquels E est exploré alphabétiquement puis stocké dans la pile.
- Le successeur du sommet E, c’est-à-dire que G est stocké dans la pile.
- Les sommets G ont deux sommets connectés, et les deux sont déjà visités. G sort donc de la pile.
- De même, E s a également été supprimé.
- Maintenant, le sommet B est au sommet de la pile, son autre noeud (sommet) F est exploré et stocké dans la pile.
- Le sommet F a deux successeurs C et D, entre eux C est traversé en premier et stocké dans la pile.
- Le sommet C n'a qu'un prédécesseur déjà visité, il est donc supprimé de la pile.
- Maintenant, le sommet D connecté à F est visité et stocké dans la pile.
- Comme le sommet D n'a pas de nœuds non visités, D est donc supprimé.
- De même, F, B et A sont également apparus.
- La sortie générée est - A, B, E, V, F, C, D.
Les applications de DFS incluent l’inspection de deux graphes connectés en bordure, d’un graphe fortement connecté, d’ un graphe acyclique et d’un ordre topologique .
Un graphe est appelé deux arêtes connectées si et seulement si il reste connecté même si l’une de ses arêtes est supprimée. Cette application est très utile dans les réseaux informatiques où la défaillance d’un lien dans le réseau n’affectera pas le réseau restant et où il serait toujours connecté.
Un graphe fortement connecté est un graphe dans lequel il doit exister un chemin entre une paire ordonnée de sommets. DFS est utilisé dans le graphe dirigé pour rechercher le chemin entre chaque paire ordonnée de sommets. DFS peut facilement résoudre les problèmes de connectivité.
Différences clés entre BFS et DFS
- BFS est un algorithme basé sur les vertex, tandis que DFS est un algorithme basé sur les bords.
- La structure de données en file d'attente est utilisée dans BFS. D'autre part, DFS utilise la pile ou la récursivité.
- L'espace mémoire est efficacement utilisé dans DFS, tandis que l'utilisation de l'espace dans BFS n'est pas efficace.
- BFS est l'algorithme optimal alors que DFS n'est pas optimal.
- DFS construit des arbres étroits et longs. Par contre, BFS construit des arbres larges et courts.
Conclusion
BFS et DFS, les deux techniques de recherche de graphes ont un temps d'exécution similaire mais une consommation d'espace différente, DFS prend un espace linéaire car nous devons mémoriser un chemin unique avec des nœuds non explorés, tandis que BFS conserve chaque nœud en mémoire.
DFS produit des solutions plus profondes et n'est pas optimal, mais il fonctionne bien lorsque la solution est dense, tandis que BFS est optimal, ce qui permet de rechercher l'objectif optimal au début.
