Visités
Dans la file
Arêtes examinées

  • Actuel
  • Dans la file
  • Visité
  • Chemin
Un clic sur un nœud choisit

En savoir plus sur le parcours en largeur

Parcours en largeur (BFS)

Le parcours en largeur explore un graphe par anneaux : d'abord chaque nœud voisin du départ, puis chaque nœud à deux arêtes, et ainsi de suite. Il le fait avec une file : premier entré, premier sorti. Cliquez sur un nœud pour partir de lui, choisissez une cible si vous voulez, et avancez pas à pas pour voir la file grandir et rétrécir, chaque nœud recevoir sa distance et un plus court chemin apparaître. Appuyez sur Lecture pour suivre le parcours, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour chercher un plus court chemin jusqu'à lui. Le nombre sur chaque nœud est sa distance au départ, et la ligne sous le graphe est la file. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Cliquez sur un nœud pour en faire le départ. Pour chercher un chemin, basculez le clic sur Cible et cliquez sur un autre nœud.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où dans le parcours.
  3. Observez la file sous le graphe et la distance sur chaque nœud. Nouveau graphe crée un autre graphe à essayer.

Comment fonctionne le parcours en largeur

Placez le nœud de départ dans une file avec la distance 0. Puis répétez : prenez le nœud en tête de file et examinez chacun de ses voisins. Un voisin pas encore vu reçoit une distance plus grande d'un que celle du nœud pris, retient ce nœud comme celui par lequel il a été atteint, et rejoint la fin de la file. Les voisins déjà vus sont ignorés. Quand la file est vide, chaque nœud accessible a sa distance.

Pourquoi il trouve les plus courts chemins

La file rend les nœuds dans l'ordre où ils ont été trouvés, et les nœuds sont trouvés anneau par anneau : tous les nœuds à distance 1 entrent dans la file avant ceux à distance 2, et ainsi de suite. La première fois qu'un nœud est atteint, c'est donc par un chemin qui a le moins d'arêtes possible. Remonter les nœuds retenus de la cible jusqu'au départ donne ce chemin. Seules les arêtes comptent ; quand les arêtes ont des longueurs différentes, il faut l'algorithme de Dijkstra.

Questions fréquemment posées

Qu'est-ce que le parcours en largeur ?

Une façon d'explorer un graphe depuis un nœud de départ en visitant d'abord tous ses voisins, puis leurs voisins, et ainsi de suite, anneau par anneau. Une file garde les nœuds dans l'ordre où ils ont été trouvés.

Le parcours en largeur trouve-t-il le plus court chemin ?

Oui, quand toutes les arêtes comptent pareil : la première fois que BFS atteint un nœud, il a utilisé le moins d'arêtes possible. Pour des arêtes de longueurs différentes, utilisez plutôt l'algorithme de Dijkstra.

Quelle est la différence entre BFS et DFS ?

Le parcours en largeur utilise une file et s'étend de façon régulière, anneau par anneau. Le parcours en profondeur utilise une pile (ou la récursivité) et suit un chemin aussi loin que possible avant de revenir en arrière. BFS trouve les plus courts chemins en arêtes ; DFS non, mais il est pratique pour trouver des cycles et pour le tri topologique.

Le parcours en largeur est-il rapide ?

Il retire chaque nœud de la file une fois et examine chaque arête depuis ses deux extrémités, donc le travail croît avec le nombre de nœuds plus le nombre d'arêtes.

Mon graphe est-il envoyé quelque part ?

Non. Le graphe est créé et parcouru dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur