Parcours de graphe

Cette simulation montre comment un ordinateur explore un graphe. Les élèves choisissent le parcours en largeur (BFS) ou en profondeur (DFS), choisissent le nœud de départ et règlent la vitesse, puis regardent les nœuds changer de couleur selon qu'ils attendent, sont traités ou sont visités. Les affichages donnent le nombre de nœuds visités, la taille de la file ou de la pile et l'ordre des visites, et un bouton construit un nouveau graphe aléatoire. Lancer les deux méthodes depuis le même départ montre que le BFS s'étend en anneaux, tandis que le DFS plonge en profondeur. Elle soutient les cours d'informatique sur les structures de données et les algorithmes.

• Lancez le BFS depuis le nœud 1 et lisez l'affichage Ordre de visite.
• Passez la Méthode sur DFS avec le même Nœud de départ et comparez l'ordre.
• Observez l'affichage Taille de la file / pile grandir et diminuer pour chaque méthode.
• Modifiez le Nœud de départ et voyez comment tout le parcours change.
• Appuyez sur Régénérer le graphe et prévoyez l'ordre avant de lancer la recherche.

1. 1Décrivez comment les parcours en largeur et en profondeur explorent un graphe.
2. 2Distinguez une file d'une pile et associez chacune à une méthode de recherche.
3. 3Prévoyez l'ordre de visite pour un petit graphe.
4. 4Expliquez pourquoi le BFS trouve les chemins comportant le moins de sauts.

Questions fréquentes des enseignants