NSI · Terminale · Structures de données
Graphes abstraits
Des sommets, des arêtes, des cycles.
En bref
Un graphe décrit des objets — les sommets — reliés par des arêtes.
Un graphe décrit des objets — les sommets — reliés par des arêtes. Contrairement à l’arbre, aucune hiérarchie n’est imposée et les cycles sont permis.
Le vocabulaire
| Terme | Sa définition |
|---|---|
| Orienté ou non | Selon que la relation a un sens : « suit » contre « est ami avec » |
| Pondéré | Chaque arête porte une valeur : distance, coût, débit |
| Le degré | Le nombre de voisins d’un sommet |
| Un chemin, un cycle | Une suite d’arêtes ; un chemin qui revient à son départ |
| Connexe | Tout sommet est atteignable depuis tout autre |
Les deux représentations
| Matrice d’adjacence | Liste d’adjacence | |
|---|---|---|
| La forme | Un tableau n × n, la case (i, j) vaut 1 s’il y a une arête | À chaque sommet, la liste de ses voisins |
| Test d’adjacence | Constant | Plus coûteux |
| Mémoire | En n² | Proportionnelle au nombre d’arêtes |
| Quand la choisir | Graphe dense et petit | Graphe grand et creux — presque tous les graphes réels |
Les deux parcours
| En largeur (BFS) | En profondeur (DFS) | |
|---|---|---|
| La structure | Une file | Une pile, ou la récursivité |
| Sa marche | Tous les voisins avant d’aller plus loin | S’enfoncer au plus loin, puis revenir |
| Son usage | Le plus court chemin en nombre d’arêtes, sur graphe non pondéré | Détecter les cycles, les composantes connexes, le tri topologique |
Dans les deux cas, il faut marquer les sommets visités. Sans cela, le moindre cycle fait boucler le programme indéfiniment — l’erreur la plus fréquente à l’écrit.
Le plus court chemin pondéré
BFS ne suffit plus dès que les arêtes portent des poids. Dijkstra choisit à chaque étape le sommet non traité le plus proche — à condition que tous les poids soient positifs.
C’est l’algorithme du GPS et du protocole de routage OSPF.
Les usages
Réseaux sociaux, cartographie et itinéraires, routage réseau, ordonnancement de tâches, moteurs de recherche, résolution de jeux.
Le choix de la représentation décide de la complexité du programme avant que le premier algorithme soit écrit.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quelle représentation d’un graphe convient à un grand graphe creux ?
2.Quel parcours donne le plus court chemin dans un graphe non pondéré ?
3.Quelle structure le parcours en profondeur utilise-t-il ?
4.Pourquoi faut-il marquer les sommets visités lors d’un parcours de graphe ?
5.Quelle condition l’algorithme de Dijkstra impose-t-il ?
6.Un graphe connexe est un graphe où tout sommet est atteignable depuis tout autre.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Graphes abstraits » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
