Parcours en largeur
Le parcours en largeur d'un graphe depuis une source : file, marquage, ordre de visite, arbre de parcours, distances en nombre d'arêtes, plus court chemin non pondéré et coût en O(n + m).
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Source : de quoi s'agit-il ?
Voir la réponse
Sommet de départ du parcours : il est à la distance 0 de lui-même et c'est le premier à entrer dans la file.
Les distances et l'arbre de parcours dépendent de la source : changer de source change l'ordre de visite.
Graphe de 8 sommets, arêtes : A-B, A-C, B-D, B-E, C-F, D-G, E-G, F-H, G-H. Voisins pris dans l'ordre alphabétique, parcours en largeur depuis D : dans quel ordre les sommets sortent-ils de la file ?
- D B G A E H C F
- D B A C F H G E
- D B G A E C H F
- D G B H E A F C
Voir la réponse
D B G A E H C F
D a pour voisins B, G (niveau 1). B ajoute A, E ; G ajoute H (E est déjà marqué) : niveau 2 = A, E, H. A ajoute C, H ajoute F : niveau 3. D B A C F H G E est le parcours en profondeur depuis D, qui s'enfonce dans une branche avant de revenir.
Le parcours en largeur utilise une … : les sommets en sortent dans l'ordre où ils y sont ….
Voir la réponse
Le parcours en largeur utilise une file : les sommets en sortent dans l'ordre où ils y sont entrés.
Un sommet à distance k est toujours découvert avant un sommet à distance k + 1, donc il sort avant lui.
File : de quoi s'agit-il ?
Voir la réponse
Structure où l'on ajoute à une extrémité, la queue, et où l'on retire à l'autre, la tête : le premier arrivé est le premier sorti.
Dans le parcours, les sommets découverts en premier sont traités en premier, ce qui impose l'ordre par niveaux. Avec une pile à la place, on obtiendrait un parcours en profondeur.