Qu'est-ce que BFS?
BFS est un algorithme utilisé pour représenter graphiquement des données ou rechercher des arbres ou traverser des structures. L'algorithme visite et marque efficacement tous les nœuds clés dans un graphique de manière précise dans le sens de la largeur.
Cet algorithme sélectionne un seul nœud (point initial ou source) dans un graphique, puis visite tous les nœuds adjacents au nœud sélectionné. Une fois que l'algorithme visite et marque le nœud de départ, il se déplace vers les nœuds non visités les plus proches et les analyse.
Une fois visités, tous les nœuds sont marqués. Ces itérations se poursuivent jusqu'à ce que tous les nœuds du graphe aient été visités et marqués avec succès. La forme complète de BFS est la recherche en largeur d'abord.
Dans ce BSF Vs. Tutoriel sur l'arbre binaire DFS, vous apprendrez:
- Qu'est-ce que BFS?
- Qu'est-ce que DFS?
- Exemple de BFS
- Exemple de DFS
- Différence entre l'arborescence binaire BFS et DFS
- Applications de BFS
- Applications de DFS
Qu'est-ce que DFS?
DFS est un algorithme permettant de rechercher ou de parcourir des graphiques ou des arbres dans le sens de la profondeur. L'exécution de l'algorithme commence au nœud racine et explore chaque branche avant de revenir en arrière. Il utilise une structure de données de pile pour se souvenir, pour obtenir le sommet suivant et pour démarrer une recherche, chaque fois qu'une impasse apparaît dans une itération. La forme complète de DFS est la recherche en profondeur d'abord.
Exemple de BFS
Dans l'exemple suivant de DFS, nous avons utilisé un graphe ayant 6 sommets.
Exemple de BFS
Étape 1)
Vous avez un graphique de sept nombres allant de 0 à 6.
Étape 2)
0 ou zéro a été marqué comme nœud racine.
Étape 3)
0 est visité, marqué et inséré dans la structure de données de la file d'attente.
Étape 4)
Les 0 nœuds adjacents et non visités restants sont visités, marqués et insérés dans la file d'attente.
Étape 5)
Les itérations de déplacement sont répétées jusqu'à ce que tous les nœuds soient visités.
Exemple de DFS
Dans l'exemple suivant de DFS, nous avons utilisé un graphe non orienté ayant 5 sommets.
Étape 1)
Nous sommes partis du sommet 0. L'algorithme commence par le mettre dans la liste visitée et en mettant simultanément tous ses sommets adjacents dans la structure de données appelée pile.
Étape 2)
Vous visiterez l'élément, qui est en haut de la pile, par exemple, 1 et allez à ses nœuds adjacents. C'est parce que 0 a déjà été visité. Par conséquent, nous visitons le sommet 2.
Étape 3)
Vertex 2 a un sommet voisin non visité dans 4. Par conséquent, nous ajoutons cela dans la pile et le visitons.
Étape 4)
Enfin, nous visiterons le dernier sommet 3, il n'a pas de nœuds adjacents non visités. Nous avons terminé le parcours du graphe à l'aide de l'algorithme DFS.
Différence entre l'arborescence binaire BFS et DFS
| BFS | DFS |
| BFS trouve le chemin le plus court vers la destination. | DFS va au bas d'un sous-arbre, puis revient en arrière. |
| La forme complète de BFS est Breadth-First Search. | La forme complète de DFS est Depth First Search. |
| Il utilise une file d'attente pour suivre le prochain emplacement à visiter. | Il utilise une pile pour suivre le prochain emplacement à visiter. |
| BFS parcourt en fonction du niveau de l'arborescence. | DFS parcourt en fonction de la profondeur de l'arbre. |
| Il est implémenté en utilisant la liste FIFO. | Il est implémenté à l'aide de la liste LIFO. |
| Il nécessite plus de mémoire que DFS. | Il nécessite moins de mémoire que BFS. |
| Cet algorithme donne la solution de chemin la moins profonde. | Cet algorithme ne garantit pas la solution de chemin le moins profond. |
| Il n'est pas nécessaire de revenir en arrière dans BFS. | Il est nécessaire de revenir en arrière dans DFS. |
| Vous ne pouvez jamais être piégé dans des boucles finies. | Vous pouvez être piégé dans des boucles infinies. |
| Si vous ne trouvez aucun objectif, vous devrez peut-être développer de nombreux nœuds avant de trouver la solution. | Si vous ne trouvez aucun objectif, le retour en arrière du nœud feuille peut se produire. |
Applications de BFS
Voici les applications de BFS:
Graphiques non pondérés:
L'algorithme BFS peut facilement créer le chemin le plus court et un arbre couvrant minimum pour visiter tous les sommets du graphe dans les plus brefs délais avec une grande précision.
Réseaux P2P:
BFS peut être implémenté pour localiser tous les nœuds les plus proches ou voisins dans un réseau peer to peer. Cela permettra de trouver les données requises plus rapidement.
Crawlers Web:
Les moteurs de recherche ou les robots d'exploration Web peuvent facilement créer plusieurs niveaux d'index en utilisant BFS. La mise en œuvre de BFS commence à partir de la source, qui est la page Web, puis elle visite tous les liens de cette source.
Diffusion réseau:
Un paquet diffusé est guidé par l'algorithme BFS pour trouver et atteindre tous les nœuds pour lesquels il a l'adresse.
Applications de DFS
Voici les applications importantes de DFS:
Graphique pondéré:
Dans un graphe pondéré, la traversée de graphe DFS génère l'arborescence du chemin le plus court et l'arborescence couvrant minimum.
Détection d'un cycle dans un graphique:
Un graphique a un cycle si nous avons trouvé un bord arrière pendant DFS. Par conséquent, nous devons exécuter DFS pour le graphique et vérifier les arêtes arrière.
Trouver son chemin:
Nous pouvons nous spécialiser dans l'algorithme DFS pour rechercher un chemin entre deux sommets.
Tri topologique:
Il est principalement utilisé pour planifier des travaux à partir des dépendances données dans le groupe de travaux. En informatique, il est utilisé dans la planification des instructions, la sérialisation des données, la synthèse logique, la détermination de l'ordre des tâches de compilation.
Recherche de composants fortement connectés d'un graphique:
Il est utilisé dans le graphe DFS lorsqu'il existe un chemin entre chaque sommet du graphe et les autres sommets restants.
Résoudre des énigmes avec une seule solution:
L'algorithme DFS peut être facilement adapté pour rechercher toutes les solutions d'un labyrinthe en incluant des nœuds sur le chemin existant dans l'ensemble visité.
DIFFÉRENCES CLÉS:
- BFS trouve le chemin le plus court vers la destination tandis que DFS va au bas d'un sous-arbre, puis revient en arrière.
- La forme complète de BFS est Breadth-First Search tandis que la forme complète de DFS est Depth First Search.
- BFS utilise une file d'attente pour suivre le prochain emplacement à visiter. alors que DFS utilise une pile pour suivre le prochain emplacement à visiter.
- BFS parcourt en fonction du niveau de l'arborescence tandis que DFS parcourt en fonction de la profondeur de l'arborescence.
- BFS est implémenté en utilisant la liste FIFO, tandis que DFS est implémenté en utilisant la liste LIFO.
- Dans BFS, vous ne pouvez jamais être piégé dans des boucles finies alors que dans DFS, vous pouvez être piégé dans des boucles infinies.