Informatique · Terminale · 1 exercice vérifié
S’entraîner : Parcours de graphes
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Parcours en profondeur d'abord (avec une pile ou par récursivité) et en largeur d'abord (avec une file) en marquant les sommets déjà visités ; chercher un chemin entre deux sommets ; repérer la présence d'un cycle ; le parcours en largeur d'un graphe non pondéré atteint chaque sommet par un chemin ayant le moins d'arêtes possible ; exemples du labyrinthe et du routage.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Graphes : vocabulaire et représentations — Structure relationnelle : sommets, arêtes (graphe non orienté) ou arcs (graphe orienté), voisins, degré, chemin ; modéliser une situation (réseau routier, réseau électrique, Internet, réseau social) par un graphe ; représenter un graphe par une matrice d'adjacence ou par des listes de successeurs (ou de prédécesseurs), passer d'une représentation à l'autre et choisir selon le traitement.
- Listes, piles et files — Structures linéaires caractérisées par leurs opérations : pile (empiler, dépiler, tester si vide ; mode LIFO, le dernier entré est le premier sorti) ; file (enfiler, défiler ; mode FIFO, le premier entré est le premier sorti) ; liste (tête et queue) ; dictionnaire (accès par clé) ; choisir la structure adaptée à une situation ; une recherche dans une liste est linéaire, un accès par clé dans un dictionnaire ne parcourt pas les éléments.
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Remise en ordre (1). Difficulté 4 sur 5. Environ 5 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 4 sur 5 · ≈ 5 minutes
Énoncé
Un graphe non orienté est donné par la liste des voisins de chaque sommet.
| Sommet | Voisins |
|---|---|
| A | B, C, E |
| B | A, C, D |
| C | A, B |
| D | B |
| E | A, F |
| F | E |
On le parcourt EN LARGEUR à partir du sommet C, en examinant toujours les voisins d'un sommet dans l'ordre alphabétique et en ignorant les sommets déjà visités.
Sommets à ranger :
A ; D ; F ; C ; B ; E
Rangez les sommets dans l'ordre où ils sont visités.
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.