Comment lancer un parcours 01 Construisez le graphe. Choisissez un préréglage et appuyez sur Construire — une Grille avec rows 4 et cols 5 donne 20 nœuds et 31 arêtes unitaires — ou dessinez des arêtes en cliquant successivement sur deux nœuds dans Déplacer / relier. 02 Choisissez BFS ou DFS dans l’onglet Parcours puis une Source ; après Construire, la source est le premier nœud du préréglage. 03 Lisez le tableau de résultats. BFS imprime l’ordre de visite, la couche maximale, les inatteignables et les arêtes d’arbre ; DFS imprime préordre, postordre et arêtes arrière ; le canevas colore les nœuds visités et les arêtes d’arbre. 04 Avancez pas à pas. Lecture, Précédent / Suivant et le curseur parcourent les mêmes instantanés, pour qu’une classe voie bouger la file ou la pile.
Exemples travaillés Chaque nombre ci-dessous est lu dans le panneau.
Exécution
Lecture
Grille 4 × 5, BFS depuis 1-1
ordre de visite 1-1 → 1-2 → 2-1 → 1-3 → 2-2 → 3-1 → … → 4-5 ; couche max 7 ; inatteignables — ; arêtes d’arbre 19
Grille 4 × 5, DFS depuis 1-1
préordre 1-1 → 1-2 → 1-3 → 1-4 → 1-5 → 2-5 → … → 4-1 ; le postordre commence 4-1 → 4-2 → 4-3 → 4-4 → 4-5 … ; arêtes arrière 31
Cycle C₅, BFS depuis A
ordre de visite A → B → E → C → D ; couche max 2 ; arêtes d’arbre 4
Cycle C₅, DFS depuis A
préordre A → B → C → D → E ; postordre E → D → C → B → A
Graphe par défaut, BFS depuis A
ordre de visite A → B → C → D → E → F ; couche max 3 ; arêtes d’arbre 5
Graphe par défaut, DFS depuis A
préordre A → B → C → D → E → F ; postordre F → E → D → C → B → A ; arêtes arrière 9
Sur la grille, BFS atteint le coin opposé en 7 sauts — la distance de Manhattan entre 1-1 et 4-5 — et ses 19 arêtes d’arbre forment un arbre couvrant des 20 nœuds.
Le piège de l’ordre identique Sur le graphe par défaut, l’ordre de visite BFS et le préordre DFS impriment la même chaîne, A → B → C → D → E → F , donc la ligne d’ordre seule n’identifie pas l’algorithme. Les autres lignes le font : BFS place F dans la couche 3 , tandis que DFS finit en F → E → D → C → B → A et compte 9 arêtes arrière. Sur un graphe non orienté, la ligne des arêtes arrière compte des arcs, pas des arêtes — la grille rapporte 31 car ses 31 arêtes sont vues par les deux bouts (19 arcs d’arbre et 12 arcs avant forment l’autre moitié de 62). Lisez tout le tableau, pas la première ligne.
Où le parcours est utile Vérifier l’accessibilité d’abord BFS énumère chaque nœud que la source ne peut pas atteindre. Construisez Random G(n,p) avec n 6, p 0.25, seed 20260731 : le canevas contient les composantes A, B, D, E, F et le C isolé, et BFS depuis A nomme C comme inatteignable — le même découpage que l’algorithme de composantes rapporte comme deux composantes, la plus grande de 5.
Enseigner la file et la pile Lancez les deux algorithmes sur C₅ depuis A. BFS s’ouvre aux deux voisins avant d’aller plus profond (A → B → E → C → D ) ; DFS s’engage dans une direction et ne revient qu’à la fin (A → B → C → D → E avec postordre E → D → C → B → A ). Le curseur d’étapes montre la frontière rétrécir dans un cas et grandir dans l’autre.
Limites Des sauts, pas des poids. Les deux parcours comptent les arêtes ; les poids saisis dans l’éditeur ne changent rien ici. Les itinéraires pondérés appartiennent au panneau plus court chemin . Une source à la fois. Il n’y a pas de BFS multi-source : lancez les sources à tour de rôle. Le panneau ne résume pas non plus tout le graphe (diamètre, maille, centralité) et ne l’ordonne pas topologiquement — cela vit dans métriques et centralité et ordre et connectivité .
La direction suit le commutateur. Sur un graphe orienté, les deux recherches ne suivent que les flèches ; les nœuds atteints par une arête entrante restent inatteignables jusqu’à ce que vous remettiez le commutateur.
Confidentialité L’édition du graphe et les deux recherches s’exécutent dans votre navigateur ; rien n’est téléversé, et le dernier graphe reste dans le stockage local jusqu’à l’effacement des données du site.
Références
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4e éd., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— BFS et DFS, discipline de file et de pile.
Wikipédia, Breadth-first search , en.wikipedia.org (访问日期:2026-10-07)— couches, distance et arêtes d’arbre.
Wikipédia, Depth-first search , en.wikipedia.org (访问日期:2026-10-07)— préordre, postordre et arêtes arrière.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07