NSI (Spé) — Structures de données
Graphes : représentation et parcours
Graphes orientés et non orientés, matrices d'adjacence, listes d'adjacence, parcours BFS et DFS
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Cours de spé NSI. Même notion dans une autre matière : Graphes : vocabulaire, représentation, parcours — Maths expertes
Résumé
Quand les relations ne sont plus hiérarchiques mais enchevêtrées, on passe aux graphes. Un graphe, ce sont des sommets reliés par des arêtes (sans direction) ou des arcs (avec direction). Un réseau d'amis, un plan de métro, le Web : tout se modélise ainsi. Deux façons de le coder s'opposent : la matrice d'adjacence, un tableau $n \times n$ rapide mais gourmand en mémoire ($O(n^2)$), idéale pour les graphes denses ; et les listes d'adjacence, un dictionnaire compact ($O(n+m)$), parfait pour les graphes creux — c'est-à-dire la quasi-totalité des graphes réels. Le bon choix de représentation conditionne l'efficacité de tous les algorithmes de parcours qui suivront.
Un graphe relie des sommets par des arêtes. Selon que ces liens ont une direction ou non, un poids ou non, on parle de graphe orienté, pondéré, etc. Ce vocabulaire décrit fidèlement quantité de situations réelles : réseaux, cartes, dépendances.
- Non orienté : les arêtes n'ont pas de sens. Si A est relié à B, alors B l'est à A (une amitié).
- Orienté (digraphe) : les arcs ont un sens. Un arc A→B n'implique pas B→A (« suivre » sur Twitter).
- Pondéré : chaque arête porte un poids (distance, coût, durée).
- Degré d'un sommet : nombre d'arêtes incidentes (en orienté : degrés entrant et sortant).
- Chemin : suite de sommets reliés ; cycle : chemin qui revient à son point de départ.
- Connexe : il existe un chemin entre toute paire de sommets.
Exemple
Réseau social : les sommets sont des personnes, les arêtes des amitiés (graphe non orienté). Le degré d'une personne est son nombre d'amis ; un chemin A → B → C relie deux personnes via un ami commun.
Piège à éviter
Twitter (les followers) est un graphe orienté : suivre quelqu'un n'oblige pas à être suivi en retour. Facebook (les amis) est non orienté. Choisir le mauvais type fausse tout le modèle.
La matrice d'adjacence est un tableau $n \times n$ où la case $(i, j)$ vaut $1$ si l'arête existe, $0$ sinon. Tester une arête est immédiat, mais la mémoire occupée est toujours $O(n^2)$, même pour un graphe presque vide.
- Tableau $n \times n$ : $M[i][j] = 1$ si l'arête $(i, j)$ existe, $0$ sinon.
- Graphe non orienté : la matrice est symétrique ($M[i][j] = M[j][i]$).
- Graphe pondéré : $M[i][j]$ contient le poids (ou $0$ / $\infty$ s'il n'y a pas d'arête).
- Avantage : tester l'existence d'une arête en $O(1)$.
- Inconvénient : mémoire en $O(n^2)$, même avec très peu d'arêtes.
- À privilégier pour les graphes denses (beaucoup d'arêtes).
Exemple
Pour le graphe d'arêtes A-B, A-C, C-D (sommets A, B, C, D indexés de 0 à 3), la ligne de A est [0, 1, 1, 0] : A est relié à B et C. La matrice est symétrique.
Piège à éviter
Pour un graphe de $10\,000$ sommets avec peu d'arêtes, une matrice gaspille $10^8$ cases. Dans ce cas, préfère les listes d'adjacence.
Les listes d'adjacence associent à chaque sommet la liste de ses voisins, en Python un dictionnaire. La mémoire ne croît qu'avec le nombre réel d'arêtes : c'est la représentation reine des graphes creux et des parcours.
Un même graphe, deux représentations : la matrice ($O(n^2)$) et les listes d'adjacence ($O(n+m)$).
- Dictionnaire : chaque clé est un sommet, chaque valeur la liste de ses voisins.
- Exemple : {'A': ['B','C'], 'B': ['A'], 'C': ['A','D'], 'D': ['C']}.
- Pondéré : on stocke des tuples (voisin, poids), ex. {'A': [('B',5), ('C',3)]}.
- Avantage : mémoire en $O(n+m)$ ($m$ = nombre d'arêtes) — efficace pour les graphes creux.
- Inconvénient : tester une arête demande de parcourir la liste des voisins (en $O(\text{degré})$).
Exemple
graphe = {'A': ['B','C'], 'B': ['A'], 'C': ['A','D'], 'D': ['C']}
# Parcourir les voisins de C :
for voisin in graphe['C']:
print(voisin) # affiche A puis D
# Parcourir les voisins de C :
for voisin in graphe['C']:
print(voisin) # affiche A puis D
Piège à éviter
Dans un graphe non orienté, une arête A-B doit figurer des deux côtés : ajouter B dans graphe['A'] et A dans graphe['B']. L'oublier rend le graphe incohérent.
Matrice ou listes ? Tout dépend de la densité du graphe et des opérations dominantes. Un mauvais choix coûte de la mémoire ou du temps ; le bon rend les algorithmes naturels.
- Graphe dense ($m \approx n^2$) → matrice. Graphe creux ($m \ll n^2$) → listes.
- La plupart des graphes réels (réseau social, routes, Web) sont creux.
- Matrice : accès direct en $O(1)$, simple à coder. Listes : économes en mémoire.
- Pour les parcours (BFS, DFS), les listes d'adjacence sont généralement préférées.
- Le choix influence la complexité : un parcours est en $O(n+m)$ avec des listes, $O(n^2)$ avec une matrice.
Exemple
Carte routière de France : des millions d'intersections (sommets), mais chacune n'a que 2 à 4 routes (arêtes). Graphe très creux → listes d'adjacence, indispensables pour tenir en mémoire.
Piège à éviter
Utiliser une matrice pour un grand graphe creux gaspille énormément de mémoire et ralentit les parcours (on examine des cases vides). Adapte toujours la structure au graphe.
Quiz - Graphes : représentation et parcours
10 questions
S'entraîner
- Quiz : Graphes : représentation et parcours10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Articles utiles
Questions fréquentes
Les points clés à retenir sur Graphes : représentation et parcours, extraits du quiz de révision.
Dans un graphe non orienté, la matrice d'adjacence est :
Réponse :
Symétrique
Dans un graphe non orienté, si l'arête (i,j) existe, alors l'arête (j,i) aussi, donc M[i][j] = M[j][i] : la matrice est symétrique.
Quelle est la complexité mémoire d'une matrice d'adjacence pour n sommets ?
Réponse :
O(n²)
La matrice d'adjacence est un tableau de taille n×n, soit O(n²) en mémoire, indépendamment du nombre d'arêtes.
Les listes d'adjacence sont préférées pour les graphes :
Réponse :
Creux (peu d'arêtes)
Les listes d'adjacence occupent O(n + m) en mémoire, ce qui est bien plus efficace que O(n²) quand le graphe a peu d'arêtes (m << n²).
Le degré d'un sommet dans un graphe non orienté est :
Réponse :
Le nombre d'arêtes incidentes à ce sommet
Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre de voisins directs de ce sommet.