Réseau routier, réseau social, plan d’un métro, liens entre pages web : dès qu’on s’intéresse à des relations entre des éléments, on peut les modéliser par un graphe. Ce chapitre présente le vocabulaire, deux façons de représenter un graphe en Python et les deux grands parcours qui servent de base à de nombreux algorithmes.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Utiliser le vocabulaire des graphes : sommet, arête, arc, voisin, degré, chemin, cycle, connexité
- Représenter un graphe par une matrice d’adjacence ou par des listes d’adjacence (dictionnaire)
- Programmer les parcours en largeur (file) et en profondeur (pile ou récursivité)
- Utiliser un parcours pour chercher un chemin ou détecter un cycle
1. Vocabulaire
Graphe : Ensemble de sommets reliés par des arêtes (graphe non orienté) ou par des arcs (graphe orienté, chaque arc ayant un sens). Un graphe est pondéré si chaque arête porte un poids (distance, coût…).
A --- B
| |
C --- D
| |
E --- F
Arêtes : A–B, A–C, B–D, C–D, C–E, D–F, E–F- Deux sommets reliés par une arête sont voisins (adjacents). Le degré d’un sommet est son nombre de voisins : dans G, C est de degré 3.
- Un chemin est une suite de sommets dont deux consécutifs sont voisins : A, C, E, F. Sa longueur est son nombre d’arêtes (ici 3).
- Un cycle est un chemin qui revient à son point de départ sans réutiliser d’arête : A, B, D, C, A.
- Un graphe non orienté est connexe si deux sommets quelconques sont toujours reliés par un chemin. G est connexe.
2. Représenter un graphe
Matrice d’adjacence : on numérote les n sommets ; le coefficient ligne i, colonne j vaut 1 s’il existe une arête (ou un arc) de i vers j, 0 sinon. Pour un graphe non orienté, la matrice est symétrique.
M = [[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0],
[0, 1, 1, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0]]Listes d’adjacence : on associe à chaque sommet la liste de ses voisins (ou de ses successeurs pour un graphe orienté). En Python, un dictionnaire est idéal.
g = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}| Matrice d’adjacence | Listes d’adjacence | |
|---|---|---|
| Mémoire | n² cases, même si le graphe a peu d’arêtes | Proportionnelle au nombre de sommets et d’arêtes |
| Tester si i et j sont voisins | Immédiat : M[i][j] | Parcours de la liste des voisins de i |
| Énumérer les voisins | Parcours d’une ligne entière (n cases) | Directement la liste |
3. Parcours en largeur
Le parcours en largeur (BFS) explore les sommets par distance croissante au sommet de départ : d’abord ses voisins, puis les voisins des voisins… Il utilise une file et un ensemble de sommets déjà découverts.
from collections import deque
def largeur(g, depart):
distance = {depart: 0}
f = deque([depart])
while len(f) > 0:
u = f.popleft()
for v in g[u]:
if v not in distance: # v découvert pour la première fois
distance[v] = distance[u] + 1
f.append(v)
return distanceParcours en largeur de G depuis A (voisins pris dans l’ordre alphabétique)
- On défile A : on découvre B et C (distance 1).
- On défile B : on découvre D (distance 2). On défile C : on découvre E (distance 2).
- On défile D : on découvre F (distance 3). E et F n’apportent plus rien.
Ordre de visite : A, B, C, D, E, F. La distance de A à F est 3 arêtes.
4. Parcours en profondeur, chemins et cycles
Le parcours en profondeur (DFS) s’enfonce le plus loin possible avant de revenir en arrière. Il s’écrit simplement de façon récursive (la pile d’appels joue le rôle de pile), ou de façon itérative avec une pile explicite.
def profondeur(g, u, visites):
visites.append(u)
for v in g[u]:
if v not in visites:
profondeur(g, v, visites)
return visites
print(profondeur(g, "A", [])) # ['A', 'B', 'D', 'C', 'E', 'F']- Chercher un chemin de s à t : on lance un parcours depuis s en mémorisant, pour chaque sommet découvert, le sommet d’où l’on vient (son « parent ») ; on remonte ensuite de t à s.
- Avec un parcours en largeur, le chemin obtenu a le plus petit nombre d’arêtes possible.
- Détecter un cycle dans un graphe non orienté : lors d’un parcours en profondeur, on rencontre un sommet déjà visité qui n’est pas le parent du sommet courant.
- Connexité : le graphe est connexe si un parcours depuis un sommet quelconque visite tous les sommets.
À retenir
- Un graphe est formé de sommets reliés par des arêtes (ou des arcs s’il est orienté).
- Matrice d’adjacence : n² cases, test d’adjacence immédiat. Listes d’adjacence : dictionnaire sommet → voisins.
- Parcours en largeur : file, sommets visités par distance croissante.
- Parcours en profondeur : pile ou récursivité.
- Les parcours permettent de trouver des chemins, de tester la connexité et de détecter des cycles.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.