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

Un graphe est une structure de données qui modélise des objets et les liens entre eux. Formellement, un graphe G est un couple G = (S, A) où :

• S est un ensemble fini de sommets (en anglais vertices, ou nodes) ;
• A est un ensemble de liens entre sommets : des arêtes si le graphe est non orienté, des arcs s'il est orienté.

De nombreuses situations se modélisent par un graphe :

Situation	Sommets	Liens
Réseau routier	Villes / carrefours	Routes
Réseau social	Personnes	Relations d'amitié
Web	Pages	Liens hypertextes (orientés)
Labyrinthe	Cases	Passages entre cases

2. Vocabulaire des graphes

On distingue deux grandes familles selon que les liens ont un sens ou non.

Graphe non orienté

Les liens sont des arêtes : une arête {u, v} relie u et v sans privilégier de sens. Si u est relié à v, alors v est relié à u (relation symétrique). On dit que u et v sont adjacents (ou voisins) et que l'arête est incidente à u et à v.

Graphe orienté

Les liens sont des arcs : un arc (u, v) va de u vers v. Le sens compte : l'arc (u, v) n'implique pas l'arc (v, u). On dit que u est le sommet de départ (origine) et v le sommet d'arrivée. v est un successeur de u, et u un prédécesseur de v.

Notion	Non orienté	Orienté
Lien	arête {u, v}	arc (u, v)
Sens	aucun (symétrique)	de u vers v
Suite de sommets	chaîne	chemin
Boucle fermée	cycle	circuit

Ordre du graphe. L'ordre d'un graphe est son nombre de sommets, noté n = |S|. On note souvent m = |A| le nombre d'arêtes (ou d'arcs). Pour un graphe simple non orienté, 0 ≤ m ≤ n(n−1)/2 ; pour un graphe simple orienté, 0 ≤ m ≤ n(n−1).

3. Degré d'un sommet

Le degré mesure le nombre de liens attachés à un sommet.

• Graphe non orienté : le degré d'un sommet u, noté deg(u), est le nombre d'arêtes incidentes à u (c.-à-d. le nombre de ses voisins).
• Graphe orienté : on distingue le degré entrant d⁻(u) (nombre d'arcs arrivant en u) et le degré sortant d⁺(u) (nombre d'arcs partant de u).

4. Chemins, chaînes, cycles et circuits

Une chaîne (graphe non orienté) ou un chemin (graphe orienté) est une suite de sommets s₀, s₁, …, s_k telle que deux sommets consécutifs sont reliés (par une arête, resp. un arc dans le bon sens). Sa longueur est le nombre de liens parcourus, soit k.

• Une chaîne/un chemin est simple si elle ne passe pas deux fois par le même sommet.
• Un cycle (non orienté) ou un circuit (orienté) est une chaîne/un chemin qui revient à son point de départ (s₀ = s_k) sans réutiliser de lien.

On dit qu'un sommet v est accessible depuis u s'il existe un chemin de u vers v. La distance entre u et v est la longueur du plus court chemin les reliant (∞ s'il n'en existe aucun).

5. Connexité

Un graphe non orienté est connexe s'il existe une chaîne entre toute paire de sommets : « on peut aller de n'importe où à n'importe où ». Sinon, le graphe se décompose en composantes connexes, chacune étant un sous-ensemble maximal de sommets deux à deux reliés.

6. Représentation : matrice d'adjacence

Numérotons les sommets de 0 à n−1. La matrice d'adjacence M est une matrice \(n \times n\) telle que :

M[i][j] = 1 s'il existe un arc/arête de i vers j,   M[i][j] = 0 sinon.

• Pour un graphe non orienté, la matrice est symétrique : M[i][j] = M[j][i].
• La diagonale est nulle (pas de boucle dans un graphe simple).

Exemple — graphe non orienté à 4 sommets avec les arêtes {0,1}, {0,2}, {1,2}, {2,3} :

       0  1  2  3
   0 [ 0  1  1  0 ]
   1 [ 1  0  1  0 ]
   2 [ 1  1  0  1 ]
   3 [ 0  0  1  0 ]

# Matrice d'adjacence en Python : liste de listes
M = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]

# Existe-t-il une arête entre 0 et 2 ?
print(M[0][2] == 1)   # True

Opération	Coût (matrice)
Test d'existence d'un arc	\(O(1)\)
Liste des voisins d'un sommet	\(O(n)\)
Mémoire utilisée	\(O(n^{2})\)

La matrice est idéale pour un graphe dense (beaucoup d'arêtes) ou quand on teste souvent l'existence d'un lien, mais elle gaspille de la mémoire pour un graphe creux.

7. Représentation : listes d'adjacence

Pour chaque sommet, on stocke la liste de ses voisins. On regroupe ces listes dans une liste (sommets numérotés) ou dans un dictionnaire (sommets quelconques).

# Listes d'adjacence dans une LISTE (sommets 0..n-1)
G = [
    [1, 2],     # voisins de 0
    [0, 2],     # voisins de 1
    [0, 1, 3],  # voisins de 2
    [2],        # voisins de 3
]

# Listes d'adjacence dans un DICTIONNAIRE
G = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C'],
}
print(G['C'])   # ['A', 'B', 'D'] : voisins de C

Opération	Coût (listes d'adj.)
Test d'existence d'un arc	\(O(deg(u))\)
Liste des voisins d'un sommet	\(O(deg(u))\)
Mémoire utilisée	\(O(n + m)\)

8. Manipulation d'un graphe en Python

Voici les opérations de base sur une représentation par dictionnaire de listes (graphe non orienté).

def ajouter_sommet(G, u):
    if u not in G:
        G[u] = []

def ajouter_arete(G, u, v):
    ajouter_sommet(G, u)
    ajouter_sommet(G, v)
    if v not in G[u]:
        G[u].append(v)
        G[v].append(u)   # non orienté : on ajoute dans les deux sens

def supprimer_arete(G, u, v):
    if v in G[u]:
        G[u].remove(v)
        G[v].remove(u)

def existe_arete(G, u, v):
    return u in G and v in G[u]

def voisins(G, u):
    return G[u]

Construire la liste des voisins d'un sommet à partir de la matrice d'adjacence est un grand classique :

def voisins_depuis_matrice(M, u):
    return [j for j in range(len(M)) if M[u][j] == 1]

M = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]
print(voisins_depuis_matrice(M, 2))   # [0, 1, 3]

9. Parcours en largeur (BFS)

Le parcours en largeur (Breadth-First Search) explore le graphe « par cercles concentriques » : d'abord le sommet de départ, puis tous ses voisins (distance 1), puis les voisins des voisins (distance 2), etc. Il utilise une file (FIFO : premier entré, premier sorti).

from collections import deque

def bfs(G, depart):
    vus = {depart}
    file = deque([depart])
    ordre = []
    while file:
        u = file.popleft()        # défile en tête (FIFO)
        ordre.append(u)
        for v in G[u]:
            if v not in vus:
                vus.add(v)
                file.append(v)    # enfile en queue
    return ordre

G = {'A':['B','C'], 'B':['A','D'], 'C':['A','D'], 'D':['B','C']}
print(bfs(G, 'A'))   # ['A', 'B', 'C', 'D']

Le BFS visite chaque sommet une fois et examine chaque arête une fois : sa complexité est \(O(n + m)\). Propriété fondamentale : dans un graphe non pondéré, le BFS calcule le plus court chemin (en nombre d'arêtes) depuis le sommet de départ.

10. Parcours en profondeur (DFS)

Le parcours en profondeur (Depth-First Search) explore « le plus loin possible » avant de revenir en arrière (backtracking). Il s'écrit naturellement de façon récursive, ou de façon itérative avec une pile (LIFO).

# Version récursive
def dfs(G, u, vus=None):
    if vus is None:
        vus = set()
    vus.add(u)
    ordre = [u]
    for v in G[u]:
        if v not in vus:
            ordre += dfs(G, v, vus)
    return ordre

# Version itérative (pile)
def dfs_iter(G, depart):
    vus = set()
    pile = [depart]
    ordre = []
    while pile:
        u = pile.pop()            # dépile au sommet (LIFO)
        if u not in vus:
            vus.add(u)
            ordre.append(u)
            for v in G[u]:
                if v not in vus:
                    pile.append(v)
    return ordre

Comme le BFS, le DFS est en \(O(n + m)\). La différence est l'ordre de visite : le BFS privilégie la largeur (file), le DFS la profondeur (pile/récursion).

11. Applications des parcours : cycle et connexité

Test de connexité (non orienté)

def est_connexe(G):
    if not G:
        return True
    depart = next(iter(G))        # un sommet quelconque
    atteints = set(bfs(G, depart))
    return len(atteints) == len(G)   # a-t-on atteint TOUS les sommets ?

Détection de cycle (non orienté)

Lors d'un DFS, si on rencontre un voisin déjà visité qui n'est pas le père dont on vient, c'est qu'il existe un cycle.

def a_un_cycle(G):
    vus = set()
    def explore(u, pere):
        vus.add(u)
        for v in G[u]:
            if v not in vus:
                if explore(v, u):
                    return True
            elif v != pere:      # voisin déjà vu, différent du père => cycle
                return True
        return False
    for s in G:
        if s not in vus:
            if explore(s, None):
                return True
    return False

12. Graphes pondérés et plus court chemin (Dijkstra)

Un graphe est pondéré quand chaque arc/arête porte une étiquette numérique (un poids ou coût) : distance, temps, prix… Le problème du plus court chemin consiste à minimiser la somme des poids le long du chemin.

En Python, on stocke le poids à côté du voisin :

# dictionnaire de listes de couples (voisin, poids)
G = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': [],
}

L'algorithme de Dijkstra calcule les plus courtes distances depuis une source, à condition que tous les poids soient positifs. Idée : à chaque étape, on « fige » le sommet non encore traité de plus petite distance estimée, puis on relâche ses arcs (on met à jour la distance de ses voisins). Une file de priorité (tas, module heapq) sélectionne efficacement ce minimum.

import heapq

def dijkstra(G, source):
    dist = {u: float('inf') for u in G}
    dist[source] = 0
    tas = [(0, source)]               # (distance, sommet)
    while tas:
        d, u = heapq.heappop(tas)     # sommet de plus petite distance
        if d > dist[u]:
            continue                  # entrée périmée
        for v, poids in G[u]:
            if dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids     # relâchement
                heapq.heappush(tas, (dist[v], v))
    return dist

print(dijkstra(G, 'A'))   # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Avec un tas, Dijkstra s'exécute en \(O((n + m) \log n)\). Note : le plus court chemin A→B passe par C (1 + 2 = 3) plutôt que par l'arc direct A→B (de poids 4).

13. Pour aller plus loin : A* et Floyd-Warshall

Algorithme A*. C'est une variante heuristique de Dijkstra. À la distance déjà parcourue g(v) on ajoute une estimation h(v) du reste à parcourir jusqu'au but (par exemple la distance à vol d'oiseau). On explore en priorité les sommets de plus petit f(v) = g(v) + h(v). Si l'heuristique ne surestime jamais la distance réelle (heuristique admissible), A* trouve le plus court chemin tout en explorant moins de sommets que Dijkstra. Très utilisé en jeux vidéo et GPS.

Floyd-Warshall. Calcule les plus courtes distances entre toutes les paires de sommets, par programmation dynamique. On améliore progressivement la distance d[i][j] en autorisant comme sommets intermédiaires 0, 1, …, k :

def floyd_warshall(d):     # d : matrice n x n des poids, inf si pas d'arc
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

Sa complexité est \(O(n^{3})\). La coloration de graphe (attribuer une couleur à chaque sommet pour que deux voisins n'aient jamais la même) est un autre classique d'application.

14. Récapitulatif

CPGE MP / PSI · Informatique — Introduction à la théorie des graphes