Algorithmes de graphes en Python : le guide pour bien démarrer

Les graphes sont partout dès que l’on modélise des relations : routes entre villes, dépendances entre tâches, liens dans un réseau social, connexions entre serveurs, graphe de connaissances, itinéraires, recommandations ou arbres de décision. En Python, les algorithmes de graphes permettent de répondre à des questions très concrètes : quels sommets sont accessibles ? Quel est le plus court chemin ? Le graphe est-il connecté ? Comment relier tous les points au coût minimal ?

La bonne nouvelle, c’est qu’il n’est pas nécessaire de commencer par une bibliothèque complexe. Avec des dictionnaires, des listes, deque et heapq, on peut déjà comprendre et implémenter les principaux algorithmes.

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

Ce simple dictionnaire suffit à représenter un graphe non pondéré. Chaque clé est un sommet, et chaque valeur contient ses voisins.

La réponse courte

Pour bien démarrer avec les graphes en Python, apprenez dans cet ordre :

1. représenter un graphe avec un dictionnaire ;
2. parcourir le graphe avec BFS et DFS ;
3. trouver des composantes connexes ;
4. calculer un plus court chemin avec Dijkstra ;
5. construire un arbre couvrant minimum avec Prim ou Kruskal ;
6. choisir la bonne structure de données selon le problème.

Le réflexe le plus important : avant de coder un algorithme, identifiez le type de graphe.

Représenter un graphe en Python

Un graphe contient des sommets et des arêtes. En Python, la représentation la plus simple est la liste d’adjacence.

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

Cette structure est pratique pour parcourir les voisins d’un sommet.

for voisin in graphe["A"]:
    print(voisin)

Pour un graphe pondéré, on stocke aussi le coût de chaque arête.

graphe_pondere = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 8)],
    "D": [("B", 5), ("C", 8)],
}

Ici, ("B", 4) signifie qu’il existe une arête vers B avec un poids de 4.

Graphe orienté ou non orienté

Dans un graphe non orienté, une arête fonctionne dans les deux sens. Si A est connecté à B, alors B est aussi connecté à A.

graphe = {
    "A": ["B"],
    "B": ["A"],
}

Dans un graphe orienté, le sens compte. Une relation de A vers B n’implique pas forcément une relation de B vers A.

graphe_oriente = {
    "A": ["B"],
    "B": [],
}

Cette distinction change le comportement des algorithmes. Un réseau routier à sens unique, un graphe de dépendances ou un flux de tâches sont souvent orientés. Un réseau de câbles, des amitiés symétriques ou des connexions physiques sont souvent non orientés.

BFS : parcourir par niveaux

BFS, pour Breadth-First Search, explore un graphe par couches. Il visite d’abord les voisins directs, puis les voisins des voisins, et ainsi de suite.

En Python, BFS s’écrit naturellement avec collections.deque.

from collections import deque


def bfs(graphe, depart):
    visites = set()
    file = deque([depart])
    ordre = []

    while file:
        sommet = file.popleft()

        if sommet in visites:
            continue

        visites.add(sommet)
        ordre.append(sommet)

        for voisin in graphe[sommet]:
            if voisin not in visites:
                file.append(voisin)

    return ordre


print(bfs(graphe, "A"))

BFS est utile pour :

• trouver les sommets accessibles ;
• calculer un plus court chemin dans un graphe non pondéré ;
• explorer par distance croissante ;
• analyser des réseaux simples.

Dans un graphe non pondéré, BFS trouve le chemin avec le plus petit nombre d’arêtes.

DFS : explorer en profondeur

DFS, pour Depth-First Search, explore un chemin aussi loin que possible avant de revenir en arrière.

Voici une version récursive :

def dfs(graphe, sommet, visites=None):
    if visites is None:
        visites = set()

    visites.add(sommet)

    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)

    return visites


print(dfs(graphe, "A"))

DFS est utile pour :

• détecter des composantes ;
• explorer des dépendances ;
• rechercher un chemin quelconque ;
• analyser des structures récursives ;
• préparer certains algorithmes plus avancés.

Attention : sur un très grand graphe, la version récursive peut atteindre la limite de récursion de Python. Dans ce cas, une version avec pile explicite est plus robuste.

def dfs_iteratif(graphe, depart):
    visites = set()
    pile = [depart]

    while pile:
        sommet = pile.pop()

        if sommet in visites:
            continue

        visites.add(sommet)

        for voisin in graphe[sommet]:
            if voisin not in visites:
                pile.append(voisin)

    return visites

Trouver les composantes connexes

Une composante connexe est un groupe de sommets reliés entre eux. Si un graphe n’est pas entièrement connecté, il contient plusieurs composantes.

def composantes_connexes(graphe):
    visites = set()
    composantes = []

    for sommet in graphe:
        if sommet in visites:
            continue

        composante = dfs_iteratif(graphe, sommet)
        composantes.append(composante)
        visites.update(composante)

    return composantes

Exemple :

graphe = {
    "A": ["B"],
    "B": ["A"],
    "C": ["D"],
    "D": ["C"],
    "E": [],
}

print(composantes_connexes(graphe))

Résultat possible :

[{"A", "B"}, {"C", "D"}, {"E"}]

Cette idée sert à comprendre si un réseau est fragmenté, si tous les sommets peuvent être atteints, ou si un algorithme doit être relancé sur plusieurs groupes.

Dijkstra : plus court chemin avec poids positifs

Dijkstra calcule les plus courts chemins depuis un sommet de départ dans un graphe pondéré avec des poids positifs.

Il utilise une file de priorité. En Python, cette file est généralement implémentée avec heapq.

import heapq


def dijkstra(graphe, depart):
    distances = {sommet: float("inf") for sommet in graphe}
    distances[depart] = 0
    tas = [(0, depart)]

    while tas:
        distance_actuelle, sommet = heapq.heappop(tas)

        if distance_actuelle > distances[sommet]:
            continue

        for voisin, poids in graphe[sommet]:
            nouvelle_distance = distance_actuelle + poids

            if nouvelle_distance < distances[voisin]:
                distances[voisin] = nouvelle_distance
                heapq.heappush(tas, (nouvelle_distance, voisin))

    return distances

Exemple :

graphe_pondere = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 8)],
    "D": [("B", 5), ("C", 8)],
}

print(dijkstra(graphe_pondere, "A"))

Dijkstra est un excellent choix pour des distances, coûts, temps de trajet ou pénalités, à condition que les poids ne soient pas négatifs.

Si votre graphe contient des poids négatifs, il faut regarder Bellman-Ford plutôt que Dijkstra.

Prim et Kruskal : relier tous les sommets au coût minimal

Prim et Kruskal servent à construire un arbre couvrant minimum. Ils ne cherchent pas le plus court chemin entre deux sommets. Ils cherchent à relier tous les sommets avec un coût total minimal, sans cycle.

Prim agrandit un arbre depuis un sommet de départ.

Kruskal trie les arêtes et ajoute les moins chères tant qu’elles ne créent pas de cycle.

La différence pratique :

Pour une explication complète avec code, voir le guide dédié : Prim vs Kruskal en Python.

Union-Find : la structure à connaître

Union-Find, ou ensembles disjoints, permet de savoir rapidement si deux sommets appartiennent déjà au même groupe.

Elle est très utile dans Kruskal, mais aussi dans plusieurs problèmes de connectivité.

class UnionFind:
    def __init__(self, elements):
        self.parent = {element: element for element in elements}

    def find(self, element):
        if self.parent[element] != element:
            self.parent[element] = self.find(self.parent[element])
        return self.parent[element]

    def union(self, a, b):
        racine_a = self.find(a)
        racine_b = self.find(b)

        if racine_a == racine_b:
            return False

        self.parent[racine_b] = racine_a
        return True

Si union(a, b) renvoie False, cela signifie que a et b étaient déjà connectés. Dans Kruskal, ajouter cette arête créerait un cycle.

Quelle structure Python utiliser ?

Le choix de la structure de données compte autant que l’algorithme.

Un bon article ou un bon code de graphe commence souvent par une représentation claire. Si la représentation est confuse, l’algorithme devient difficile à relire.

Complexités à retenir

Les complexités dépendent de :

• V, le nombre de sommets ;
• E, le nombre d’arêtes.

Ces ordres de grandeur ne remplacent pas les tests, mais ils donnent un bon réflexe : plus le graphe est grand, plus la représentation et la structure de données deviennent importantes.

Erreurs fréquentes avec les graphes en Python

Confondre plus court chemin et arbre couvrant minimum

Dijkstra répond à la question : “quelle est la distance minimale depuis ce sommet vers les autres ?”

Prim et Kruskal répondent à la question : “comment relier tous les sommets au coût total minimal ?”

Ces deux problèmes se ressemblent visuellement, mais ils sont différents.

Oublier le deuxième sens dans un graphe non orienté

Si l’arête A-B existe dans un graphe non orienté, il faut ajouter B dans les voisins de A, et A dans les voisins de B.

graphe["A"].append("B")
graphe["B"].append("A")

Utiliser une liste au lieu d’un set pour les visites

Pour vérifier rapidement si un sommet a déjà été vu, utilisez un set.

visites = set()

Avec une liste, les tests d’appartenance deviennent plus coûteux à mesure que le graphe grandit.

Appliquer Dijkstra avec des poids négatifs

Dijkstra suppose que les poids sont positifs ou nuls. Si votre graphe contient des poids négatifs, le résultat peut être incorrect. Dans ce cas, Bellman-Ford est plus adapté.

Laisser le code dépendre de l’ordre des voisins

Selon la structure utilisée, l’ordre de parcours peut varier. Si vous voulez un résultat reproductible dans un tutoriel ou un test, triez les voisins.

for voisin in sorted(graphe[sommet]):
    ...

Mini-exercice : choisir le bon algorithme

Pour chaque cas, choisissez l’algorithme le plus adapté.

Ces choix couvrent une grande partie des problèmes de graphes rencontrés en Python.

Le parcours recommandé

Si vous apprenez les graphes, ne commencez pas par les algorithmes les plus avancés. Suivez plutôt ce chemin :

1. représentation par dictionnaire ;
2. BFS sur un graphe non pondéré ;
3. DFS récursif et itératif ;
4. composantes connexes ;
5. Dijkstra avec heapq ;
6. Prim et Kruskal ;
7. Union-Find ;
8. Bellman-Ford, Floyd-Warshall et A*.

Ce parcours évite un piège classique : apprendre des noms d’algorithmes sans comprendre le problème qu’ils résolvent.

Pour aller plus loin

Vous pouvez compléter ce guide avec les articles déjà disponibles :

• Dijkstra en Python : trouver le chemin le plus court depuis un sommet donné ;
• implémenter l’algorithme de Prim en Python ;
• implémenter l’algorithme de Kruskal en Python ;
• Prim vs Kruskal en Python : choisir le bon algorithme de graphe ;
• trouver les composantes connexes en Python.

L’objectif n’est pas de mémoriser tous les algorithmes d’un coup. L’objectif est de savoir reconnaître la forme du problème. Une fois la bonne question posée, le bon algorithme devient beaucoup plus évident.

Références

• Documentation Python – collections.deque
• Documentation Python – heapq
• Documentation Python – types set
• Wikipedia – Graph traversal
• Wikipedia – Dijkstra’s algorithm