Question 1

Matrice d'adjacence ou listes d'adjacence : laquelle choisir ?

Accepted Answer

Pour n sommets numérotés de 0 à n - 1, la matrice s'écrit `M = [[0] * n for i in range(n)]`, puis `M[u][v] = 1` pour chaque arête ; les listes s'écrivent `G = [[] for i in range(n)]`, puis `G[u].append(v)`, et une arête d'un graphe non orienté y est rangée deux fois. La matrice teste une arête en O(1), mais occupe n^2 cases quel que soit le nombre d'arêtes et demande O(n) pour trouver les voisins d'un sommet. Les listes occupent O(n + p), pour p arêtes, donnent les voisins aussitôt, mais testent une arête en O(d(i)). Pour 1 000 sommets de quatre voisins chacun, la matrice a un million de cases, les listes 4 000 éléments. La matrice convient aux petits graphes et aux graphes denses ; les listes d'adjacence conviennent aux graphes peu denses, comme les réseaux réels, et aux parcours.

Question 2

Comment écrire un parcours en largeur en Python ?

Accepted Answer

Avec une file : `from collections import deque`, `F = deque()`, `F.append(s)` et `vu[s] = True` pour le départ. Tant que la file n'est pas vide, on retire `u = F.popleft()`, on le traite, puis on examine ses voisins dans l'ordre de la liste : chaque voisin non marqué est marqué aussitôt et enfilé. On marque un sommet au moment où on l'enfile, pour qu'il n'entre qu'une fois dans la file. On n'écrit jamais `F.pop(0)` sur une liste : ce retrait décale tous les éléments et coûte O(k) pour une file de k éléments ; mesuré sur 160 000 éléments, vider la file ainsi est environ 300 fois plus lent qu'avec `popleft`, en temps constant.

Question 3

Comment trouver un plus court chemin avec un parcours en largeur ?

Accepted Answer

On initialise `dist` à -1 partout sauf `dist[s] = 0`, et `pred` à -1. Pendant le parcours en largeur, quand on découvre v depuis u, on pose `dist[v] = dist[u] + 1` et `pred[v] = u`. Les sommets sortent de la file par distances croissantes : à la fin, `dist[v]` est la distance de s à v en nombre d'arêtes. Pour obtenir un plus court chemin jusqu'à t, on remonte `pred` depuis t jusqu'à s, puis on retourne la liste ; si `dist[t]` vaut -1, t n'est pas accessible. Le coût est celui du parcours, O(n + p). Ce chemin est le plus court en nombre d'arêtes, pas en kilomètres : sur les pistes du cours, il rend un itinéraire de 45 km alors qu'un autre, avec le même nombre de pistes, en fait 37. Les longueurs relèvent d'autres algorithmes, au chapitre suivant.

Question 4

Parcours en profondeur : version récursive ou avec une pile ?

Accepted Answer

La version récursive visite un sommet, le marque, puis s'appelle sur chacun de ses voisins non vus. Elle empile un appel par sommet de la chaîne en cours, et Python limite par défaut la pile à 1 000 appels en attente : sur une chaîne de 2 000 sommets parcourue depuis une extrémité, elle s'arrête sur une erreur `RecursionError`. La version avec une pile explicite dépile un sommet, le marque et le visite s'il n'est pas encore vu, puis empile ses voisins non vus ; un sommet peut alors être empilé plusieurs fois, et la pile contenir jusqu'à O(p) éléments. Les deux sont des parcours en profondeur, mais pas dans le même ordre : la pile prend d'abord le dernier voisin de la liste. Empiler les voisins en ordre inverse redonne l'ordre de la version récursive. Pour un très grand graphe, on préfère la version avec une pile.

Question 5

Quelle est la complexité d'un parcours en largeur ou en profondeur ?

Accepted Answer

Avec des listes d'adjacence, O(n + p) : chaque sommet est enfilé ou visité au plus une fois, puisqu'on le marque, et chaque liste d'adjacence est parcourue une fois ; la somme de leurs longueurs vaut 2p dans un graphe non orienté, puisque la somme des degrés vaut 2p. Avec une matrice, trouver les voisins d'un sommet lit une ligne entière, en O(n) : le parcours coûte O(n^2), même si le graphe a peu d'arêtes. Le meilleur cas, un départ sans voisin, est en Θ (n), pour la création de la liste `vu` ; le pire cas, tous les sommets accessibles, en Θ (n + p) avec des listes et en Θ (n^2) avec une matrice. Pour 4 000 sommets et environ 8 000 arêtes, le parcours en largeur prend environ 5 ms avec des listes et 2 s avec une matrice.

Question 6

Comment tester la connexité d'un graphe ou y détecter un cycle ?

Accepted Answer

Un graphe non orienté est connexe si un parcours depuis un sommet quelconque atteint les n sommets. Pour les composantes connexes, on lance un parcours depuis chaque sommet non encore atteint et l'on donne le même numéro à tous les sommets qu'il atteint : O(n + p) en tout. Pour un cycle dans un graphe non orienté, on retient le père de chaque sommet découvert : un voisin déjà marqué qui n'est pas le père révèle un cycle ; l'arête qui ramène au père, elle, n'en fait pas. Dans un graphe orienté, rencontrer un sommet déjà vu ne prouve rien, car deux chemins peuvent arriver au même sommet : on fait un parcours en profondeur à trois états, non vu, en cours, terminé, et un arc vers un sommet en cours ferme un circuit. Ces tests coûtent O(n + p) avec des listes d'adjacence.

opération	matrice	listes d'adjacence
tester l'arête $\{i, j\}$	$O(1)$	$O(d(i))$
voisins de $s$	$O(n)$	$O(d(s))$
degré	$O(n)$	$O(1)$
ajouter un sommet	$O(n^2)$	$O(1)$
mémoire	$O(n^2)$	$O(n + p)$
parcours complet	$O(n^2)$	$O(n + p)$

tour	retiré	enfilés	file après le tour
1	0	1, 2	`[1, 2]`
2	1	3	`[2, 3]`
3	2	aucun	`[3]`
4	3	4, 5	`[4, 5]`
5	4	aucun	`[5]`
6	5	aucun	`[]`

Graphes : représentations en Python, parcours en largeur et en profondeur, exercices corrigés de prépa

Ce que tu sauras faire

L'essentiel : Coûts selon la représentation Extrait gratuit

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Plan du cours

Les méthodes du chapitre

Les exercices corrigés

Application directe (13)

Entraînement (15)

Approfondissement (6)

Les problèmes de concours

Questions fréquentes

Comment y accéder

Toute ta prépa au même endroit