Le moins d'arrêts possible
Tu pars de la gare. Tu veux aller à la piscine en changeant le moins possible. Tu regardes le plan de la ville.
Une bonne idée : d'abord les lieux à une arête de la gare. Puis ceux à deux arêtes. Puis ceux à trois. Comme des cercles qui grandissent autour de la gare.
C'est le parcours en largeur. Tu as vu les graphes dans la leçon « Les graphes » et les files dans « Les files d'attente ».
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Graphe | Des sommets reliés entre eux par des arêtes. | Le plan de la ville |
| Sommet | Un lieu du graphe. | Gare |
| Arête | Un trait qui relie deux sommets. | Gare et Mairie |
| Voisin | Un sommet relié directement à un autre. | Parc est voisin de Gare |
| Distance | Le plus petit nombre d’arêtes à suivre entre deux sommets. | De Gare à Piscine : 3 |
| File | Une liste où le premier arrivé est le premier servi. | La file de la cantine |
| Sommet vu | Un sommet déjà mis dans la file. On ne le remet jamais. | Gare, dès le départ |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : lire le plan
À toi de jouer
À toi : lire le plan
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
L'idée : des cercles qui grandissent
On met le départ dans une file. Puis on répète : on retire le premier de la file, et on met dans la file tous ses voisins qui ne sont pas encore vus.
Comme la file sert le premier arrivé en premier, les lieux proches passent avant les lieux lointains. On s'arrête quand la file est vide.
Exemple travaillé : la file, depuis Gare
| Étape | On retire | Nouveaux voisins mis dans la file | La file après |
|---|---|---|---|
| 0 | - | - | Gare |
| 1 | Gare | Mairie, Parc | Mairie, Parc |
| 2 | Mairie | Cinema, Stade (Gare est déjà vu) | Parc, Cinema, Stade |
| 3 | Parc | Aucun (Gare et Stade sont vus) | Cinema, Stade |
| 4 | Cinema | Piscine | Stade, Piscine |
| 5 | Stade | Aucun | Piscine |
| 6 | Piscine | Aucun | File vide : fini |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : la file à la main
À toi de jouer
À toi : la file à la main
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.