🎯 Objectifs de la lecon
- •Savoir représenter un graphe par matrice d'adjacence
- •Savoir représenter un graphe par liste d'adjacence
- •Comprendre et implémenter le parcours en largeur (BFS)
- •Comprendre et implémenter le parcours en profondeur (DFS)
Un graphe modélise des relations entre des objets. En NSI, tu dois savoir le représenter en mémoire et le parcourir efficacement.
Définition d'un graphe
Un graphe est un ensemble de sommets (ou nœuds) reliés par des arêtes. Si les arêtes sont orientées, on parle de graphe orienté. Sinon, il est non orienté.
Exemple : un réseau social. Chaque utilisateur est un sommet. Chaque lien d'amitié est une arête non orientée.
✔️ A retenir
Un graphe G = (S, A) où S est l'ensemble des sommets et A l'ensemble des arêtes.
Représentation par matrice d'adjacence
La matrice d'adjacence est un tableau carré de taille n × n, où n est le nombre de sommets. La case (i, j) vaut 1 s'il existe une arête du sommet i vers le sommet j, et 0 sinon.
Pour un graphe non orienté, la matrice est symétrique : si (i, j) vaut 1, alors (j, i) vaut aussi 1.
« Graphe à 3 sommets (0,1,2) avec arêtes 0-1 et 1-2. Matrice : [[0,1,0],[1,0,1],[0,1,0]]. »
Point fort : La matrice permet de tester l'existence d'une arête en temps constant O(1).
⚠️ Attention
La matrice d'adjacence utilise O(n²) mémoire, même si le graphe a peu d'arêtes. Elle est adaptée aux graphes denses.
Représentation par liste d'adjacence
La liste d'adjacence associe à chaque sommet la liste de ses voisins. En Python, on utilise un dictionnaire dont les clés sont les sommets et les valeurs des listes.
« Même graphe : {0: [1], 1: [0, 2], 2: [1]}. Chaque sommet pointe vers ses voisins directs. »
Point fort : La mémoire utilisée est O(n + m) où m est le nombre d'arêtes. C'est efficace pour les graphes creux.
✔️ A retenir
Matrice d'adjacence : rapide pour tester une arête, mais coûteuse en mémoire. Liste d'adjacence : économique, mais tester une arête peut prendre O(deg(ré)) en moyenne.
Parcours en largeur (BFS)
Le parcours en largeur (Breadth-First Search) explore un graphe niveau par niveau. Il utilise une file (FIFO) pour stocker les sommets à visiter.
On commence par un sommet source. On le marque visité, on l'ajoute à la file. Tant que la file n'est pas vide, on retire le premier sommet, on visite tous ses voisins non visités, on les marque et on les ajoute à la file.
« Graphe 0-1-2, source 0. File : [0]. On retire 0, on ajoute 1. File : [1]. On retire 1, on ajoute 2. File : [2]. On retire 2. Ordre : 0, 1, 2. »
Point fort : BFS donne le plus court chemin en nombre d'arêtes dans un graphe non pondéré.
⚠️ Attention
Ne pas oublier de marquer un sommet visité avant de l'ajouter à la file, sinon il pourrait être ajouté plusieurs fois.
Parcours en profondeur (DFS)
Le parcours en profondeur (Depth-First Search) explore un graphe en allant le plus loin possible avant de revenir en arrière. Il utilise une pile (LIFO) ou la récursivité.
On part d'un sommet source. On le marque visité. Pour chaque voisin non visité, on appelle récursivement DFS sur ce voisin. Quand tous les voisins sont visités, on remonte.
« Graphe 0-1-2, source 0. Visite 0, puis 1, puis 2. Ordre : 0, 1, 2. Si le graphe avait une branche plus longue, DFS irait jusqu'au bout avant de revenir. »
Point fort : DFS utilise moins de mémoire que BFS si le graphe est profond et peu large.
✔️ A retenir
BFS : file, ordre par niveaux. DFS : pile ou récursif, ordre en profondeur. Les deux visitent tous les sommets accessibles.
Erreurs fréquentes
- Confondre matrice et liste d'adjacence : la matrice est un tableau 2D, la liste est un dictionnaire de listes.
- Oublier de marquer un sommet visité dans BFS : cela peut créer une boucle infinie.
- Utiliser une pile pour BFS : BFS nécessite une file, DFS une pile.
- Croire que BFS donne toujours le plus court chemin : c'est vrai seulement pour les graphes non pondérés.
