Les graphes sont une structure de données incontournable en NSI, surtout en Terminale. Que ce soit pour modéliser un réseau social, un labyrinthe ou un itinéraire, tu vas les croiser souvent. Mais attention : plusieurs pièges guettent les lycéens. Dans cet article, on va voir les 3 erreurs les plus fréquentes sur les graphes en NSI, et surtout comment les éviter. Prêt·e à devenir un as des graphes ?
Erreur n°1 : confondre liste d'adjacence et matrice d'adjacence
En NSI, on représente souvent un graphe par une liste d'adjacence (dictionnaire) ou une matrice d'adjacence. L'erreur classique est de ne pas choisir la bonne représentation selon le contexte, ou de les confondre.
Quand utiliser quoi ?
- Liste d'adjacence : idéale pour les graphes creux (peu d'arêtes). Rapide pour lister les voisins d'un sommet (complexité O(1) en moyenne).
- Matrice d'adjacence : parfaite pour les graphes denses (beaucoup d'arêtes). Permet de tester rapidement si une arête existe (O(1)), mais prend plus de mémoire.
Exemple en Python :
# Liste d'adjacence (dictionnaire)
graphe = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
# Matrice d'adjacence (liste de listes)
sommets = ['A', 'B', 'C', 'D']
matrice = [
[0, 1, 1, 0], # A
[1, 0, 0, 1], # B
[1, 0, 0, 0], # C
[0, 1, 0, 0] # D
]À retenir : en NSI, la liste d'adjacence est souvent plus pratique pour les parcours (BFS, DFS). Ne la confonds pas avec la matrice !
Erreur n°2 : oublier de gérer les visites dans un parcours de graphe
Quand tu fais un parcours de graphe (BFS ou DFS), il est crucial de marquer les sommets déjà visités pour éviter les boucles infinies. L'erreur fréquente : ne pas initialiser ou mettre à jour la structure de visite.
Exemple : BFS sans gestion des visites
from collections import deque
def bfs_erreur(graphe, depart):
file = deque([depart])
while file:
sommet = file.popleft()
print(sommet)
for voisin in graphe[sommet]:
file.append(voisin) # Oups ! On ajoute sans vérifier
Ce code boucle indéfiniment si le graphe a un cycle.
La bonne version :
def bfs_correct(graphe, depart):
visites = set()
file = deque([depart])
visites.add(depart)
while file:
sommet = file.popleft()
print(sommet)
for voisin in graphe[sommet]:
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
Pense toujours à marquer un sommet comme visité dès que tu l'ajoutes à la file/pile, pas quand tu le dépiles. Sinon, tu risques d'ajouter plusieurs fois le même sommet.
Erreur n°3 : négliger la complexité mémoire et temporelle
En NSI, on te demande souvent d'analyser la complexité. Beaucoup d'élèves oublient que la mémoire utilisée par une matrice d'adjacence est en O(n��) où n est le nombre de sommets. Pour un graphe de 10 000 sommets, c'est 100 millions de cases !
De même, un parcours en profondeur récursif peut provoquer un dépassement de pile (stack overflow) si le graphe est trop profond. Préfère une version itérative avec une pile explicite.
# DFS itératif (pile explicite)
def dfs_iteratif(graphe, depart):
visites = set()
pile = [depart]
while pile:
sommet = pile.pop()
if sommet not in visites:
visites.add(sommet)
print(sommet)
for voisin in graphe[sommet]:
if voisin not in visites:
pile.append(voisin)
Bon réflexe : avant d'implémenter, demande-toi : combien de sommets ? d'arêtes ? Quelle est la structure la plus adaptée ?
Cas d'usage concret : modéliser un réseau social
Imaginons un petit réseau social avec des utilisateurs et des amitiés. On veut trouver la distance entre deux personnes (nombre d'amis intermédiaires). C'est un cas typique d'utilisation d'un parcours en largeur (BFS).
def distance_amis(graphe, depart, arrivee):
if depart == arrivee:
return 0
visites = {depart}
file = deque([(depart, 0)])
while file:
sommet, dist = file.popleft()
for voisin in graphe[sommet]:
if voisin == arrivee:
return dist + 1
if voisin not in visites:
visites.add(voisin)
file.append((voisin, dist + 1))
return -1 # pas de chemin
Cet algorithme est exact et efficace. Fais attention à ne pas oublier le marquage des visites (erreur n°2) et à bien choisir la structure (liste d'adjacence ici, erreur n°1).
Conseils pour le bac NSI et les révisions
Pour l'épreuve de NSI, tu dois maîtriser :
- Les différentes représentations (liste/matrice) et savoir les implémenter.
- Les algorithmes de parcours (BFS, DFS) et leur complexité.
- Savoir appliquer les graphes à des problèmes concrets (chemins, cycles, etc.).
Entraîne-toi sur les exercices du site https://www.nsi-lycee.fr/exercices et consulte les fiches de révision sur https://www.nsi-lycee.fr/fiches. Pour approfondir, jette un œil aux cours sur https://www.nsi-lycee.fr/cours.
Si tu as besoin d'aide personnalisée, n'hésite pas à consulter les ressources d'AlloBac ou AlloLycée.
Conclusion
Les graphes ne sont pas si compliqués quand on évite ces trois erreurs :
- Bien choisir sa représentation (liste vs matrice).
- Gérer les visites dans les parcours.
- Penser à la complexité mémoire et temporelle.
Avec un peu de pratique, tu deviendras incollable. Continue à coder et à explorer !
