Les graphes

Comment utiliser cette page

Cette page suit toujours le même plan : le vocabulaire, la définition, quelques usages concrets, un exemple unique (repris dans toute la page), puis les deux façons courantes d'implémenter un graphe en Python — la liste d'adjacence et la matrice d'adjacence — avant la conversion entre les deux et la complexité.

1. Vocabulaire à connaître avant de commencer

Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.

2. Qu'est-ce qu'un graphe ?

Chaque liaison possède une extrémité initiale et une extrémité terminale. Lorsque cette distinction compte, on parle d'arc et le graphe est dit orienté ; lorsqu'elle ne compte pas, on parle d'arête et le graphe est dit non orienté.

3. À quoi sert un graphe ?

Un graphe permet de représenter des relations entre des objets. Par exemple, un réseau de transport pondéré, où chaque arête porte la distance (en km) entre deux villes :

Un réseau social se représente par un graphe orienté (la relation « suit » n'est pas forcément réciproque), et un réseau informatique (ordinateurs, imprimante, routeurs reliés par des câbles) se représente naturellement par un graphe non orienté, où chaque sommet est un appareil et chaque arête une connexion physique.

4. L'exemple utilisé dans toute la suite de cette page

On reprend le même graphe à 8 sommets dans toute la suite de la page : sa version orientée (avec des arcs) pour la section sur la liste d'adjacence, et sa version non orientée (les mêmes sommets, mais reliés par des arêtes) pour la section sur la matrice d'adjacence — pour bien voir la différence entre les deux notions sur un exemple identique par ailleurs.

4.1 — Version orientée

V = {1, 2, 3, 4, 5, 6, 7, 8}

E = {(1,2), (1,5), (1,8), (2,3), (3,1), (3,4), (4,8), (5,6), (7,6), (8,7)}

4.2 — Version non orientée

Les mêmes 8 sommets, mais avec des arêtes (sans sens de parcours) plutôt que des arcs :

E = {{1,2}, {1,3}, {1,5}, {1,8}, {2,3}, {3,4}, {4,8}, {5,6}, {6,7}, {7,8}}

5. Implémentation 1 : la liste d'adjacence

On utilise un dictionnaire Python : chaque sommet est une clé, et la valeur associée est la liste de ses successeurs (pour un graphe orienté) ou de ses voisins (pour un graphe non orienté).

5.1 — Les opérations primitives

5.2 — Le code Python

def creer_graphe():
    return {}

def est_dans(G, v):
    return v in G

def ajouter_sommet(G, v):
    G[v] = []

def supprimer_sommet(G, v):
    del G[v]
    for sommet in G:
        if v in G[sommet]:
            G[sommet].remove(v)

def ajouter_arc(G, v1, v2):
    G[v1].append(v2)

def supprimer_arc(G, v1, v2):
    G[v1].remove(v2)

def successeurs(G, v):
    if est_dans(G, v):
        return G[v]
    else:
        return []

5.3 — Construire pas à pas la liste d'adjacence de l'exemple

1. Ajouter les 8 sommets 1 à 8 : chacun démarre avec une liste de successeurs vide.
2. Ajouter l'arc (1,2) : 2 rejoint la liste de 1.
3. Ajouter l'arc (1,5) : 5 rejoint la liste de 1.
4. Ajouter l'arc (1,8) : 8 rejoint la liste de 1.
5. Ajouter l'arc (2,3) : 3 rejoint la liste de 2.
6. Ajouter l'arc (3,1) : 1 rejoint la liste de 3.
7. Ajouter l'arc (3,4) : 4 rejoint la liste de 3.
8. Ajouter l'arc (4,8) : 8 rejoint la liste de 4.
9. Ajouter l'arc (5,6) : 6 rejoint la liste de 5.
10. Ajouter l'arc (7,6) : 6 rejoint la liste de 7.
11. Ajouter l'arc (8,7) : 7 rejoint la liste de 8.

G = creer_graphe()for v in [1, 2, 3, 4, 5, 6, 7, 8]:    ajouter_sommet(G, v)ajouter_arc(G, 1, 2)ajouter_arc(G, 1, 5)ajouter_arc(G, 1, 8)ajouter_arc(G, 2, 3)ajouter_arc(G, 3, 1)ajouter_arc(G, 3, 4)ajouter_arc(G, 4, 8)ajouter_arc(G, 5, 6)ajouter_arc(G, 7, 6)ajouter_arc(G, 8, 7)

On retrouve, une fois toutes ces instructions exécutées, exactement le graphe de la section 4.1 : G[1] == [2, 5, 8], G[2] == [3], G[3] == [1, 4], G[4] == [8], G[5] == [6], G[6] == [], G[7] == [6], G[8] == [7].

6. Implémentation 2 : la matrice d'adjacence

On utilise cette fois une matrice carrée (un tableau à double entrée) : les lignes représentent les sommets de départ, les colonnes les sommets d'arrivée. Une entrée nulle indique qu'il n'y a pas de liaison entre ces deux sommets ; une valeur non nulle indique l'existence d'un arc (ou d'une arête), avec une éventuelle pondération.

6.1 — Un premier exemple, pondéré et orienté

Sur un petit graphe à 3 sommets A, B, C, avec des arcs pondérés (y compris des boucles, un arc d'un sommet vers lui-même) : A→A (0,1), A→B (0,5), A→C (0,4), B→B (0,35), B→C (0,65), C→A (0,8), C→C (0,2). On dispose les sommets dans l'ordre alphabétique en ligne et en colonne, et on part d'une ligne i vers une colonne j :

En Python, une matrice se représente comme un tableau de tableaux (une liste de listes) :

graph_proba = [[0.1, 0.5, 0.4],
               [0,   0.35, 0.65],
               [0.8, 0,   0.2]]

Cette matrice n'est pas symétrique (par exemple, ligne A colonne C vaut 0.4, mais ligne C colonne A vaut 0.8) : c'est normal, ce graphe est orienté.

6.2 — Construire la matrice du graphe non orienté de l'exemple

On applique maintenant la même idée à la version non orientée de l'exemple de la section 4.2. Comme le graphe est non orienté, chaque arête {i, j} remplit deux cases symétriques : ligne i colonne j, et ligne j colonne i.

Toutes les autres cases restent à 0. On obtient la matrice suivante (les sommets 1 à 8 sont dans l'ordre, en ligne comme en colonne) :

6.3 — Le code Python

def creer_matrice(n):
    return [[0] * n for _ in range(n)]

def est_dans_matrice(matrice, i):
    return 0 <= i < len(matrice)

def ajouter_arc_matrice(matrice, i, j, poids=1):
    matrice[i][j] = poids

def supprimer_arc_matrice(matrice, i, j):
    matrice[i][j] = 0

def successeurs_matrice(matrice, i):
    n = len(matrice)
    return [j for j in range(n) if matrice[i][j] != 0]

Ici, les sommets sont numérotés de 0 à n-1 (l'indice dans la matrice), plutôt que d'avoir un nom quelconque comme avec un dictionnaire : c'est la principale différence pratique entre les deux implémentations.

7. Passer d'une représentation à l'autre

On peut convertir une matrice d'adjacence en liste d'adjacence (par sommets numérotés), et inversement.

def matrice_vers_listes_succ(matrice):
    listes_succ = {i: [] for i in range(len(matrice))}   # Initialisation des listes de successeurs
    for i in range(len(matrice)):
        for j in range(len(matrice[i])):
            if matrice[i][j] == 1:      # S'il y a une arête de i vers j
                listes_succ[i].append(j)
    return listes_succ

def listes_succ_to_matrice(listes_succ):
    n = len(listes_succ)                 # Nombre de sommets
    matrice = [[0] * n for _ in range(n)]  # Initialisation de la matrice
    for i in listes_succ:
        for j in listes_succ[i]:
            matrice[i][j] = 1             # Ajout des arêtes
    return matrice

Par exemple, avec la petite matrice [[0, 1, 0], [0, 0, 1], [1, 0, 0]] (un cycle 0 → 1 → 2 → 0), matrice_vers_listes_succ renvoie {0: [1], 1: [2], 2: [0]}.

8. Récapitulatif des complexités

n désigne le nombre de sommets du graphe, et m le nombre d'arcs (ou d'arêtes).

En résumé : la liste d'adjacence est en général plus efficace pour ajouter ou retirer des sommets, et pour obtenir directement les successeurs d'un sommet. La matrice, elle, permet de tester en O(1) si un arc précis existe entre deux sommets donnés, et son inconvénient (le nombre de cases, n²) devient négligeable quand le graphe est très dense (beaucoup d'arcs par rapport au nombre de sommets).

9. Points clés à retenir

• Un graphe est formé de deux ensembles : les sommets (V) et les liaisons entre eux (E).
• Un arc est orienté (un départ, une arrivée) ; une arête ne l'est pas.
• Dans une liste d'adjacence, chaque sommet (clé d'un dictionnaire) est associé à la liste de ses successeurs ou voisins.
• Dans une matrice d'adjacence, chaque case ligne i colonne j indique s'il existe un arc de i vers j (et son poids éventuel).
• Une matrice d'adjacence symétrique correspond toujours à un graphe non orienté, et réciproquement.
• La liste d'adjacence est adaptée quand le graphe change souvent de sommets ; la matrice est adaptée pour tester rapidement l'existence d'un arc précis, surtout sur un graphe dense.
• Un arbre binaire est un cas particulier de graphe (orienté, sans cycle, chaque sommet a au plus un père).