Numérique et sciences informatiques · Terminale · Algorithmique · 5.º Período

Algorithmes sur les graphes

Parcours de graphes en largeur et en profondeur. Recherche de chemins, détection de cycles et applications pratiques.

En bref:Les algorithmes sur les graphes sont au cœur des technologies de navigation et de recommandation. En Terminale NSI, les élèves apprennent à explorer ces structures via les parcours en largeur (BFS) et en profondeur (DFS). Ils découvrent comment ces méthodes permettent de répondre à des questions fondamentales : existe-t-il un chemin entre deux points ? Le graphe contient-il des cycles ?

• Programmes Officiels
• BOEN spécial n°8 du 25 juillet 2019 - Algorithmique
• Compétence : Parcourir un graphe en profondeur et en largeur

À propos de ce thème

Les algorithmes sur les graphes sont au cœur des technologies de navigation et de recommandation. En Terminale NSI, les élèves apprennent à explorer ces structures via les parcours en largeur (BFS) et en profondeur (DFS). Ils découvrent comment ces méthodes permettent de répondre à des questions fondamentales : existe-t-il un chemin entre deux points ? Le graphe contient-il des cycles ?

Ce chapitre fait le pont entre l'abstraction mathématique et l'utilité pratique. Les élèves voient comment un simple algorithme peut résoudre des problèmes complexes comme la sortie d'un labyrinthe ou la détection de dépendances circulaires dans un logiciel. L'utilisation de jeux de rôles ou de défis collaboratifs sur des graphes géants permet de rendre ces explorations concrètes et de bien distinguer l'usage des piles et des files dans ces parcours.

Questions clés

1. Quelle est la différence entre un parcours en largeur et en profondeur ?
2. Comment détecter un cycle dans un graphe ?
3. Comment trouver un chemin entre deux sommets ?

Attention à ces idées reçues

Idée reçue courante

Oublier de marquer les sommets déjà visités.

Ce qu'il faut enseigner à la place

Cela mène à une boucle infinie si le graphe contient un cycle. Faire vivre cette boucle infinie à un élève lors d'une simulation physique rend l'importance du marquage inoubliable.

Idée reçue courante

Confondre la structure de données utilisée pour BFS et DFS.

Ce qu'il faut enseigner à la place

BFS utilise une file (FIFO) et DFS une pile (LIFO). Faire manipuler ces deux structures côte à côte pour un même graphe permet de voir immédiatement la différence dans l'ordre de découverte des sommets.

Idées d'apprentissage actif

Jeu de simulation

Le labyrinthe humain

La salle de classe est transformée en graphe. Un élève doit trouver la sortie en utilisant strictement un algorithme de parcours en profondeur, en marquant les 'sommets' déjà visités avec des jetons.

45 min·Classe entière

Cercle de recherche

Détection de cycles

Les groupes reçoivent des graphes de dépendances de tâches. Ils doivent appliquer manuellement un parcours pour identifier s'il y a un blocage (cycle) qui empêche de terminer le projet.

40 min·Petits groupes

Penser-Partager-Présenter

BFS ou DFS ?

On présente un problème de recherche du chemin le plus court (non pondéré). Les élèves débattent en binômes pour savoir quel parcours est le plus efficace et pourquoi.

30 min·Binômes

Questions fréquentes

Quelle est la différence entre un parcours en largeur et en profondeur ?

Le parcours en largeur (BFS) explore les voisins proches avant de s'éloigner, ce qui est idéal pour trouver le chemin le plus court. Le parcours en profondeur (DFS) s'enfonce le plus loin possible dans une branche avant de reculer.

Comment détecter un cycle dans un graphe ?

Lors d'un parcours, si l'on rencontre un sommet déjà marqué comme 'en cours de visite' (pour un graphe orienté) ou déjà visité (sous certaines conditions), c'est qu'il existe un cycle.

À quoi servent ces parcours dans la vie réelle ?

Ils servent à tout : trouver un itinéraire sur un GPS, analyser les réseaux sociaux, indexer les pages web par les moteurs de recherche ou encore résoudre des puzzles complexes.

Comment l'apprentissage actif aide-t-il à comprendre les parcours de graphes ?

Les parcours de graphes demandent une grande rigueur dans le suivi des états (visité, en cours, non visité). En matérialisant ces états avec des codes couleurs ou des objets physiques lors d'une simulation en groupe, les élèves comprennent l'aspect systématique de l'algorithme, ce qui réduit les erreurs de logique lors de l'implémentation.