Théorie des graphes en pratique : modéliser, BFS, DFS et Dijkstra en Python

📍 Guide principal : Mathématiques appliquées à l’informatique : le socle pratique
Ce tutoriel approfondit la partie théorie des graphes du guide principal — à parcourir d’abord pour situer ce qu’un graphe modélise dans le code de production.

La théorie des graphes est l’un des rares pans de l’informatique théorique dont presque chaque métier tire quelque chose chaque mois. Un développeur back-end qui résout l’ordre de démarrage de microservices fait du tri topologique. Une équipe data qui calcule l’influence dans un réseau social fait du PageRank. Un ingénieur infrastructure qui traque un nœud lent dans une topologie réseau parcourt un graphe. Un développeur de jeu qui calcule le chemin d’un agent fait du A*. Pourtant, beaucoup de ces tâches sont implémentées au feeling, avec des structures inadaptées et des bugs subtils. Ce tutoriel pose, étape par étape, les fondations pratiques pour modéliser un graphe, choisir la bonne représentation, implémenter BFS, DFS et Dijkstra, et reconnaître quand un problème industriel se ramène à l’un d’eux.

Prérequis

• Python 3.10 ou plus récent
• Bibliothèque networkx (optionnelle, pour la dernière étape)
• Niveau attendu : intermédiaire — vous savez écrire une fonction récursive et utiliser des structures comme dict, set, deque
• Temps estimé : 2 heures pour parcourir et exécuter chaque étape

Étape 1 — Choisir la bonne représentation

Un graphe se représente principalement de deux façons : la matrice d’adjacence et la liste d’adjacence. Le choix conditionne la complexité de tous les algorithmes qui s’y appliquent. La matrice d’adjacence est un tableau 2D de taille V×V où la cellule (i,j) vaut 1 (ou un poids) si l’arête existe — accès en O(1) mais O(V²) en mémoire, prohibitif au-delà de quelques milliers de sommets. La liste d’adjacence stocke pour chaque sommet la liste de ses voisins — O(V+E) en mémoire, parcours rapide des voisins, mais test d’existence d’arête en O(degré). En production, sauf graphe très dense (E ≈ V²), la liste d’adjacence est presque toujours préférable.

# graph_repr.py — deux représentations équivalentes du même graphe
# Sommets : A, B, C, D, E
# Arêtes pondérées : A-B(4), A-C(2), B-D(5), C-D(1), D-E(7), C-E(3)

# Liste d'adjacence (recommandée)
adj_list = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 1), ("E", 3)],
    "D": [("B", 5), ("C", 1), ("E", 7)],
    "E": [("C", 3), ("D", 7)],
}

# Matrice d'adjacence (pour comparaison)
nodes = ["A", "B", "C", "D", "E"]
INF = float("inf")
adj_matrix = [[INF]*5 for _ in range(5)]
for i in range(5): adj_matrix[i][i] = 0
edges = [("A","B",4),("A","C",2),("B","D",5),("C","D",1),("D","E",7),("C","E",3)]
for u, v, w in edges:
    i, j = nodes.index(u), nodes.index(v)
    adj_matrix[i][j] = w
    adj_matrix[j][i] = w

print("Voisins de C (liste) :", adj_list["C"])
print("A → B (matrice) :", adj_matrix[0][1])

L’exécution affiche la liste des voisins de C avec leurs poids et le poids de l’arête A-B (4) lu via la matrice. Comparez la concision des deux structures pour ce graphe à 5 sommets : la liste d’adjacence stocke 12 entrées (chaque arête est listée deux fois car le graphe est non orienté), la matrice en stocke 25. L’écart est encore raisonnable ici, mais sur un graphe à 100 000 sommets et 1 million d’arêtes, la matrice exigerait 10 Go contre 16 Mo pour la liste — d’où l’importance du choix.

Étape 2 — Implémenter le parcours en largeur (BFS)

Le parcours en largeur visite les sommets par ondes successives à partir d’un sommet source : d’abord les voisins directs, puis les voisins des voisins, et ainsi de suite. Sa propriété fondamentale est de découvrir le plus court chemin en nombre d’arêtes dans un graphe non pondéré. C’est l’algorithme à dégainer dès qu’on cherche une distance topologique : « combien de degrés de séparation ? », « combien de redirections HTTP avant la cible ? », « quelle est la profondeur minimale dans cet arbre de catégories ? ».

# bfs.py — parcours en largeur avec distances et chemin
from collections import deque

def bfs(graph, start, target=None):
    visited = {start: 0}
    parents = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == target: break
        for neighbor, _ in graph.get(node, []):
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                parents[neighbor] = node
                queue.append(neighbor)
    return visited, parents

graph = {
    "A": [("B", 1), ("C", 1)], "B": [("A", 1), ("D", 1)],
    "C": [("A", 1), ("D", 1), ("E", 1)],
    "D": [("B", 1), ("C", 1), ("E", 1)], "E": [("C", 1), ("D", 1)],
}
distances, parents = bfs(graph, "A", target="E")
print("Distances depuis A :", distances)

# Reconstruction du chemin A → E
path, cur = [], "E"
while cur is not None:
    path.append(cur); cur = parents[cur]
print("Chemin A → E :", " → ".join(reversed(path)))

Le script affiche les distances depuis A vers chaque sommet atteint, puis reconstruit le chemin A → C → E (longueur 2). La structure clé est la deque qui sert de file FIFO — c’est elle qui garantit que les sommets sont explorés par ordre croissant de distance. La complexité est O(V + E) : chaque sommet est mis dans la file au plus une fois, chaque arête est examinée au plus deux fois (une dans chaque sens, pour un graphe non orienté). Toute implémentation BFS qui n’a pas cette complexité contient un bug — typiquement un test d’appartenance dans une liste au lieu d’un set.

Étape 3 — Implémenter le parcours en profondeur (DFS)

Le parcours en profondeur explore une branche jusqu’au bout avant de remonter. Il s’écrit naturellement par récursion ou avec une pile explicite. Ses propriétés intéressent moins la distance que la structure : DFS découvre les composantes connexes, détecte les cycles, ordonne topologiquement un graphe orienté acyclique (DAG), et calcule les composantes fortement connexes via l’algorithme de Tarjan ou Kosaraju.

# dfs.py — DFS récursif avec ordres de découverte et de fin
def dfs(graph, start):
    visited = set()
    discovery, finish = {}, {}
    counter = [0]
    def visit(node):
        visited.add(node)
        counter[0] += 1
        discovery[node] = counter[0]
        for neighbor, _ in graph.get(node, []):
            if neighbor not in visited:
                visit(neighbor)
        counter[0] += 1
        finish[node] = counter[0]
    visit(start)
    return discovery, finish

graph = {
    "A": [("B", 1), ("C", 1)], "B": [("D", 1)],
    "C": [("D", 1), ("E", 1)], "D": [("E", 1)], "E": [],
}
disc, fin = dfs(graph, "A")
print("Découverte :", disc)
print("Fin        :", fin)

Le script affiche les ordres de découverte et de fin pour chaque sommet — deux compteurs qui permettent ensuite de classifier les arêtes (arbre, retour, descendance, croisement) et de détecter les cycles. Si une arête mène d’un sommet en cours d’exploration vers un de ses ancêtres dans l’arbre DFS (arête de retour), il y a un cycle. Cette technique est utilisée par npm, pip ou cargo pour détecter les dépendances circulaires avant de lancer une installation, et c’est elle qui empêche un système de build de boucler indéfiniment.

Étape 4 — Implémenter Dijkstra avec un tas binaire

Dijkstra calcule le plus court chemin depuis un sommet source vers tous les autres dans un graphe à arêtes pondérées positives. L’algorithme maintient un ensemble de sommets dont la distance minimale est définitive, et étend itérativement cet ensemble en choisissant à chaque étape le sommet de distance minimale parmi ceux encore à traiter. Une file de priorité (tas binaire, heapq en Python) ramène la complexité à O((V + E) log V) contre O(V²) pour une implémentation naïve.

# dijkstra.py — plus court chemin pondéré
import heapq

def dijkstra(graph, source):
    distances = {node: float("inf") for node in graph}
    distances[source] = 0
    parents = {node: None for node in graph}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > distances[u]: continue
        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                parents[v] = u
                heapq.heappush(heap, (new_dist, v))
    return distances, parents

graph = {
    "A": [("B", 4), ("C", 2)], "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 1), ("E", 3)],
    "D": [("B", 5), ("C", 1), ("E", 7)], "E": [("C", 3), ("D", 7)],
}
dist, par = dijkstra(graph, "A")
print("Distances depuis A :", dist)

# Reconstruction A → E
cur, path = "E", []
while cur is not None:
    path.append(cur); cur = par[cur]
print("Chemin A → E :", " → ".join(reversed(path)))

Le script affiche un dictionnaire de distances optimales depuis A et reconstruit le plus court chemin A → C → E (poids 5). Notez l’idiome if d > distances[u]: continue qui jette les entrées obsolètes du tas : on ne supprime pas les anciennes valeurs quand on en pousse une nouvelle, on les ignore quand on les ressort. C’est plus simple et plus rapide qu’un tas indexé. Important : Dijkstra suppose que tous les poids sont positifs ou nuls. Pour des arêtes négatives, il faut Bellman-Ford ou Johnson, et pour le plus court chemin entre toutes les paires, Floyd-Warshall avec sa complexité O(V³).

Étape 5 — Détecter un cycle dans un graphe orienté

La détection de cycle est l’application la plus courante du DFS dans le code métier. Quand on charge des dépendances entre tâches, modules ou services, un cycle est presque toujours un bug à signaler. La technique standard utilise trois couleurs : blanc (non visité), gris (en cours d’exploration), noir (totalement exploré). Une arête vers un nœud gris signale un cycle.

# detect_cycle.py
WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {n: WHITE for n in graph}
    cycle_path = []
    def visit(u, path):
        color[u] = GRAY
        path.append(u)
        for v, _ in graph.get(u, []):
            if color[v] == GRAY:
                cycle_path.extend(path[path.index(v):] + [v])
                return True
            if color[v] == WHITE and visit(v, path):
                return True
        path.pop()
        color[u] = BLACK
        return False
    for u in graph:
        if color[u] == WHITE and visit(u, []):
            return True, cycle_path
    return False, None

# Graphe avec cycle B → C → D → B
graph = {
    "A": [("B", 1)], "B": [("C", 1)],
    "C": [("D", 1)], "D": [("B", 1), ("E", 1)], "E": [],
}
found, path = has_cycle(graph)
print("Cycle :", found, "—", " → ".join(path) if path else "")

Le script détecte le cycle B → C → D → B et l’affiche. La complexité est O(V + E), identique au DFS de base. Cette technique est ce qui permet à un build system comme Make, Bazel ou Rake de signaler proprement un cycle plutôt que de boucler indéfiniment, et c’est elle qu’il faut implémenter dans tout système qui charge des modules avec dépendances.

Étape 6 — Tri topologique pour orchestrer des dépendances

Sur un graphe orienté acyclique (DAG), le tri topologique produit un ordre tel que toute arête (u, v) implique u avant v dans l’ordre. C’est exactement ce qu’on veut pour démarrer des microservices dont certains dépendent d’autres, ou pour exécuter des tâches d’un pipeline ETL. L’algorithme le plus simple — Kahn 1962 — consomme itérativement les sommets sans prédécesseur.

# topo_sort.py
from collections import deque

def topo_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v, _ in graph[u]:
            in_degree[v] = in_degree.get(v, 0) + 1
    queue = deque([u for u, d in in_degree.items() if d == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v, _ in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    if len(order) != len(in_degree): raise ValueError("graphe cyclique")
    return order

# A doit démarrer avant B et C ; B et C avant D ; D avant E
graph = {"A":[("B",1),("C",1)], "B":[("D",1)], "C":[("D",1)], "D":[("E",1)], "E":[]}
print("Ordre topologique :", topo_sort(graph))

Le script affiche un ordre valide tel que ['A', 'B', 'C', 'D', 'E'] ou ['A', 'C', 'B', 'D', 'E'] — il peut y avoir plusieurs ordres valides. La complexité est O(V + E). Si vous obtenez l’exception « graphe cyclique », c’est que votre DAG n’en est pas un et vous avez un cycle à corriger en amont. Cet algorithme est ce qui anime les ordonnanceurs de pipelines (Apache Airflow, Prefect, Dagster) sous le capot.

Étape 7 — Passer à NetworkX pour les graphes industriels

Pour les graphes de plus de quelques milliers de sommets ou pour des algorithmes plus avancés (PageRank, centrality, communauté), NetworkX est la référence Python. Bibliothèque mature, elle implémente proprement BFS, DFS, Dijkstra et des dizaines d’autres algorithmes, et s’intègre avec les formats de données standards (GraphML, JSON, edge list, GEXF).

pip install networkx

L’installation prend quelques secondes et n’a pas de dépendance native. Vérifiez la sortie Successfully installed networkx-... avant de continuer. La documentation officielle est exhaustive et le projet est maintenu activement.

# networkx_demo.py
import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([("A","B",4),("A","C",2),("B","D",5),
                            ("C","D",1),("D","E",7),("C","E",3)])

print("Plus court chemin A → E :", nx.shortest_path(G, "A", "E", weight="weight"))
print("Distance A → E         :", nx.shortest_path_length(G, "A", "E", weight="weight"))
print("Centralité de proximité:", {n: round(c, 3) for n, c in nx.closeness_centrality(G).items()})

Le script affiche le plus court chemin A → C → E (distance 5) et la centralité de proximité de chaque nœud — une métrique qui mesure à quel point un sommet est central dans le graphe. Pour les graphes orientés, utilisez nx.DiGraph(). Pour la performance sur des graphes massifs (plusieurs millions de sommets), basculez vers graph-tool (C++ avec bindings Python) ou des moteurs spécialisés comme Neo4j ou JanusGraph.

Erreurs fréquentes

Tutoriels associés

• Notation big-O et analyse de complexité : mesurer le coût d’un algorithme
• Logique booléenne pour développeurs : tables de vérité, simplification et code

Pour aller plus loin

• 🔝 Retour au guide principal : Mathématiques appliquées à l’informatique : le socle pratique
• Documentation officielle NetworkX : networkx.org/documentation/stable/
• Cours MIT 6.006 — Introduction to Algorithms (modules graphes) : ocw.mit.edu/courses/6-006
• Edsger W. Dijkstra — A Note on Two Problems in Connexion with Graphs, Numerische Mathematik 1, 269-271 (1959)
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), MIT Press, chapitres 22 à 25

FAQ

Quand utiliser BFS plutôt que DFS ?

BFS dès qu’on cherche une distance ou un plus court chemin en nombre d’arêtes ; DFS pour les questions structurelles (cycles, composantes connexes, tri topologique, exploration exhaustive d’un arbre de décision). En pratique, on utilise BFS pour les recherches « lien le plus court » et DFS pour les analyses « tout l’arbre ».

Pourquoi Dijkstra et pas A* ?

A* étend Dijkstra avec une heuristique qui guide la recherche vers la cible. Quand la distance euclidienne ou une autre métrique admissible est disponible (cartes, jeux), A* est plus rapide en pratique. Sans heuristique fiable, A* dégénère en Dijkstra. Pour un graphe abstrait sans notion de proximité géométrique, Dijkstra reste le bon choix par défaut.

Comment représenter un graphe à un million de sommets en mémoire ?

Liste d’adjacence avec des entiers comme identifiants de sommets (pas des chaînes), structures compactes (numpy arrays ou scipy.sparse), et pour les graphes vraiment massifs, basculer vers une base orientée graphes (Neo4j, JanusGraph) ou un moteur de calcul distribué (GraphX, Pregel). Au-delà de cent millions d’arêtes, le RAM d’une machine standard sature : on entre dans le domaine du calcul distribué.

BFS itératif ou DFS récursif : performance comparée ?

BFS doit être itératif (la file ne se prête pas à la récursion), DFS peut être l’un ou l’autre. La récursion est plus lisible mais limite la profondeur (en Python, environ 1000 par défaut). Pour les graphes profonds (chaînes de plus de 1000 sommets), implémenter DFS avec une pile explicite ou augmenter sys.setrecursionlimit.

Comment tester unitairement un algorithme de graphe ?

Trois familles de tests : sur des graphes minimaux (graphe vide, un sommet, deux sommets, cycle, arbre), sur des graphes connus avec résultats vérifiés à la main (le graphe de Königsberg pour Euler, le graphe complet K5 pour planar), et sur des graphes aléatoires comparés à networkx comme oracle. Le property-based testing (Hypothesis) génère automatiquement les graphes minimaux qui font tomber un bug.