Graphes • Terminale NSI
Graphes et Parcours - Épreuve Pratique
⏱️ 55 min📊 Avancé⭐ 170 XP
🌊 BFS - Parcours en Largeur
- 📦 Utilise une FILE (FIFO)
- 📊 Explore niveau par niveau
- 🎯 Trouve le plus court chemin
- 💾 Mémoire : O(largeur de l'arbre)
🏔️ DFS - Parcours en Profondeur
- 📦 Utilise une PILE (LIFO)
- 📊 Explore en profondeur d'abord
- 🎯 Détecte les cycles, composantes
- 💾 Mémoire : O(hauteur de l'arbre)
🎯 Objectifs de l'épreuve
- ✓Représenter un graphe (matrice et liste d'adjacence)
- ✓Implémenter le parcours en largeur (BFS)
- ✓Implémenter le parcours en profondeur (DFS)
- ✓Détecter un chemin entre deux sommets
⚠️ Erreurs fréquentes à éviter
- ✗Oublier de marquer les sommets visités → boucle infinie
- ✗Confondre pile (DFS) et file (BFS)
- ✗Ne pas gérer les graphes non connexes
📚 Exercices type BAC
🎯 Quiz de révision
1. Quelle structure de données utilise le BFS ?
2. Le DFS explore les sommets :
3. Pour trouver le plus court chemin, on utilise :
4. La complexité du BFS sur un graphe avec V sommets et E arêtes est :
5. Dans une matrice d'adjacence, graphe[i][j] = 1 signifie :
