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
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.
- 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
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
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.