Graphes

Contenu

Graphes#

Les arbres, étudiés au chapitre précédent, imposent une structure hiérarchique stricte : un unique chemin relie deux nœuds quelconques, et il n’y a pas de cycle. Dès que l’on veut modéliser des situations plus générales — un réseau routier, un graphe de dépendances, un réseau social, un circuit électronique, un labyrinthe — on a besoin d’une structure plus souple : le graphe.

Les graphes constituent l’une des structures les plus riches et les plus étudiées de l’informatique. Les deux algorithmes de parcours fondamentaux — le parcours en profondeur (DFS) et le parcours en largeur (BFS) — servent de socle à des dizaines d’algorithmes plus avancés : chemins les plus courts, arbres couvrants, détection de cycles, tri topologique, composantes connexes, et bien d’autres encore.

Définitions fondamentales#

Graphe non orienté

Un graphe non orienté est un couple $G = (V, E)$ où :

$V$ est un ensemble fini de sommets (vertices) ;
$E \subseteq \{\{u, v\} \mid u, v \in V,\, u \neq v\}$ est un ensemble d”arêtes (edges), chaque arête étant un ensemble non ordonné de deux sommets distincts.

On note $n = |V|$ le nombre de sommets et $m = |E|$ le nombre d’arêtes.

Graphe orienté

Un graphe orienté (ou digraphe) est un couple $G = (V, A)$ où $A \subseteq V \times V$ est un ensemble d”arcs (directed edges). Un arc $(u, v)$ est distinct de $(v, u)$ : il va de $u$ vers $v$.

Variantes de graphes

Graphe pondéré : chaque arête (ou arc) porte un poids (coût, distance, capacité…). Formellement, c’est un triplet $(V, E, w)$ avec $w : E \to \mathbb{R}$.
Multigraphe : plusieurs arêtes peuvent relier la même paire de sommets.
Graphe simple : au plus une arête entre deux sommets, sans boucle ($u \neq v$ pour toute arête).
Graphe connexe : tout sommet est accessible depuis tout autre par un chemin.
Graphe acyclique dirigé (DAG) : graphe orienté sans cycle.

Degré

Dans un graphe non orienté, le degré d’un sommet $v$, noté $\deg(v)$, est le nombre d’arêtes qui lui sont incidentes. Dans un graphe orienté, on distingue le degré entrant $\deg^-(v)$ (nombre d’arcs entrant en $v$) et le degré sortant $\deg^+(v)$ (nombre d’arcs sortant de $v$).

Lemme des poignées de main : dans tout graphe non orienté, $\sum_{v \in V} \deg(v) = 2|E|$.

Représentations en mémoire#

Le choix de la représentation a un impact direct sur la complexité des algorithmes. Les deux représentations principales sont la matrice d’adjacence et la liste d’adjacence.

Matrice d’adjacence#

Matrice d’adjacence

La matrice d’adjacence d’un graphe $G = (V, E)$ est une matrice $A \in \{0, 1\}^{n \times n}$ définie par : $$A[i][j] = \begin{cases} 1 & \text{si } (i, j) \in E \\ 0 & \text{sinon} \end{cases}$$ Pour un graphe non orienté, $A$ est symétrique. Pour un graphe pondéré, on stocke $w(i,j)$ au lieu de $1$.

Espace : $O(n^2)$. Accès à $(i,j)$ : $O(1)$. Parcours des voisins de $i$ : $O(n)$.

Liste d’adjacence#

Liste d’adjacence

La liste d’adjacence représente le graphe par un tableau de $n$ listes (ou ensembles). La liste $\text{adj}[v]$ contient tous les voisins de $v$.

Espace : $O(n + m)$. Parcours des voisins de $v$ : $O(\deg(v))$. Accès à $(u, v)$ : $O(\deg(u))$.

Note

La liste d’adjacence est presque toujours préférable pour les graphes creux ($m \ll n^2$), ce qui est le cas de la plupart des graphes réels (réseaux sociaux, graphes routiers). La matrice d’adjacence est utile quand le graphe est dense ($m \approx n^2$) ou quand on a besoin de tester l’existence d’une arête en $O(1)$ très fréquemment.

class Graphe:
    """Graphe non orienté représenté par une liste d'adjacence."""

    def __init__(self, n_sommets):
        self.n = n_sommets
        self.adj = defaultdict(set)

    def ajouter_arete(self, u, v):
        self.adj[u].add(v)
        self.adj[v].add(u)

    def voisins(self, v):
        return self.adj[v]

    def sommets(self):
        return range(self.n)

    def nb_aretes(self):
        return sum(len(vois) for vois in self.adj.values()) // 2

    def degre(self, v):
        return len(self.adj[v])

    def vers_matrice(self):
        """Retourne la matrice d'adjacence (liste de listes)."""
        M = [[0] * self.n for _ in range(self.n)]
        for u in self.adj:
            for v in self.adj[u]:
                M[u][v] = 1
        return M

    def __repr__(self):
        lignes = [f"Graphe à {self.n} sommets, {self.nb_aretes()} arêtes"]
        for v in range(self.n):
            lignes.append(f"  {v} → {sorted(self.adj[v])}")
        return '\n'.join(lignes)


# Exemple de graphe
G = Graphe(6)
for u, v in [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5)]:
    G.ajouter_arete(u, v)

print(G)
print()

# Matrice d'adjacence
M = G.vers_matrice()
print("Matrice d'adjacence :")
for i, ligne in enumerate(M):
    print(f"  {i} | {ligne}")

Graphe à 6 sommets, 8 arêtes
→ [1, 2]
→ [0, 2, 3]
→ [0, 1, 4]
→ [1, 4, 5]
→ [2, 3, 5]
→ [3, 4]

Matrice d'adjacence :
| [0, 1, 1, 0, 0, 0]
| [1, 0, 1, 1, 0, 0]
| [1, 1, 0, 0, 1, 0]
| [0, 1, 0, 0, 1, 1]
| [0, 0, 1, 1, 0, 1]
| [0, 0, 0, 1, 1, 0]

_images/64a0cfd0fc1e0cc47e9e568441d5772239c08f400fbbf1ef6df28ace44fd1969.png

Parcours en profondeur (DFS)#

Parcours en profondeur

Le parcours en profondeur (Depth-First Search, DFS) explore un graphe en s’enfonçant le plus loin possible dans chaque direction avant de revenir en arrière (backtracking). L’algorithme peut être implémenté récursivement (en utilisant la pile d’appels) ou itérativement (en maintenant une pile explicite).

def dfs_recursif(graphe, depart, visites=None, ordre=None):
    """DFS récursif. Retourne l'ordre de visite des sommets."""
    if visites is None:
        visites = set()
        ordre = []
    visites.add(depart)
    ordre.append(depart)
    for voisin in sorted(graphe.voisins(depart)):  # tri pour reproductibilité
        if voisin not in visites:
            dfs_recursif(graphe, voisin, visites, ordre)
    return ordre


def dfs_iteratif(graphe, depart):
    """DFS itératif avec une pile explicite."""
    visites = set()
    pile = [depart]
    ordre = []
    while pile:
        sommet = pile.pop()
        if sommet in visites:
            continue
        visites.add(sommet)
        ordre.append(sommet)
        # Ajouter les voisins non visités (en ordre inverse pour reproductibilité)
        for voisin in sorted(graphe.voisins(sommet), reverse=True):
            if voisin not in visites:
                pile.append(voisin)
    return ordre


print("DFS récursif  depuis 0 :", dfs_recursif(G, 0))
print("DFS itératif  depuis 0 :", dfs_iteratif(G, 0))

DFS récursif  depuis 0 : [0, 1, 2, 4, 3, 5]
DFS itératif  depuis 0 : [0, 1, 2, 4, 3, 5]

Note

La complexité du DFS est $O(n + m)$ avec une représentation par liste d’adjacence. Chaque sommet est marqué visité une seule fois, et chaque arête est examinée au plus deux fois (une par extrémité dans un graphe non orienté). Avec une matrice d’adjacence, la complexité devient $O(n^2)$ car il faut parcourir toute une ligne pour trouver les voisins.

Arbre DFS et arêtes de retour#

Lors d’un DFS, les arêtes du graphe se répartissent en plusieurs catégories :

Arêtes d’arbre (tree edges) : les arêtes empruntées pour découvrir un nouveau sommet.
Arêtes de retour (back edges) : les arêtes reliant un sommet à l’un de ses ancêtres dans l’arbre DFS (uniquement dans les graphes non orientés ou orientés avec cycles).
Arêtes directes (forward edges) et arêtes croisées (cross edges) : uniquement dans les graphes orientés.

Détection de cycles via le DFS

Dans un graphe non orienté, un cycle existe si et seulement si le DFS découvre une arête de retour (une arête vers un sommet déjà visité qui n’est pas le parent direct dans l’arbre DFS).

Dans un graphe orienté, on utilise le système de coloration : blanc (non visité), gris (en cours d’exploration), noir (entièrement traité). Une arête vers un sommet gris indique la présence d’un cycle.

def detecter_cycle_non_oriente(graphe):
    """Détecte un cycle dans un graphe non orienté par DFS. O(n + m)."""
    visite = set()

    def dfs(sommet, parent):
        visite.add(sommet)
        for voisin in graphe.voisins(sommet):
            if voisin not in visite:
                if dfs(voisin, sommet):
                    return True
            elif voisin != parent:
                # Arête de retour vers un sommet qui n'est pas le parent
                return True
        return False

    for s in graphe.sommets():
        if s not in visite:
            if dfs(s, -1):
                return True
    return False


def detecter_cycle_oriente(adj, n):
    """Détecte un cycle dans un graphe orienté par DFS avec coloration. O(n + m)."""
    # 0 = blanc, 1 = gris, 2 = noir
    couleur = [0] * n

    def dfs(v):
        couleur[v] = 1  # gris : en cours
        for voisin in adj.get(v, []):
            if couleur[voisin] == 1:
                return True   # arête vers gris → cycle
            if couleur[voisin] == 0:
                if dfs(voisin):
                    return True
        couleur[v] = 2  # noir : terminé
        return False

    for s in range(n):
        if couleur[s] == 0:
            if dfs(s):
                return True
    return False


print("Cycle dans G :", detecter_cycle_non_oriente(G))

# Graphe sans cycle (arbre)
arbre_g = Graphe(5)
for u, v in [(0, 1), (0, 2), (1, 3), (1, 4)]:
    arbre_g.ajouter_arete(u, v)
print("Cycle dans l'arbre :", detecter_cycle_non_oriente(arbre_g))

Cycle dans G : True
Cycle dans l'arbre : False

Parcours en largeur (BFS)#

Parcours en largeur

Le parcours en largeur (Breadth-First Search, BFS) explore un graphe niveau par niveau. Il utilise une file (FIFO) et calcule, pour chaque sommet, sa distance (en nombre d’arêtes) au sommet source.

def bfs(graphe, depart):
    """
    BFS depuis 'depart'. Retourne (ordre_visite, distances).
    distances[v] = nombre d'arêtes entre depart et v.
    """
    visite = {depart}
    file = deque([depart])
    ordre = []
    distances = {depart: 0}

    while file:
        sommet = file.popleft()
        ordre.append(sommet)
        for voisin in sorted(graphe.voisins(sommet)):
            if voisin not in visite:
                visite.add(voisin)
                distances[voisin] = distances[sommet] + 1
                file.append(voisin)

    return ordre, distances


ordre_bfs, dist = bfs(G, 0)
print("BFS depuis 0 :", ordre_bfs)
print("Distances depuis 0 :", dist)

BFS depuis 0 : [0, 1, 2, 3, 4, 5]
Distances depuis 0 : {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}

Note

Le BFS calcule les plus courts chemins (en nombre d’arêtes) entre la source et tous les sommets accessibles, dans un graphe non pondéré. La complexité est $O(n + m)$ avec une liste d’adjacence. Le BFS est à la base des algorithmes de plus court chemin non pondérés, de la détection de bipartition, et de nombreuses autres applications.

_images/ce9feffc50f99714ee634bda73f9f9528093a96f86c6e754c88692dbb1e9ac7a.png

Composantes connexes#

Composante connexe

Une composante connexe d’un graphe non orienté est un sous-graphe maximal dans lequel tout sommet est accessible depuis tout autre par un chemin. Un graphe est connexe s’il ne possède qu’une seule composante connexe.

def composantes_connexes(graphe):
    """
    Retourne la liste des composantes connexes d'un graphe non orienté.
    Chaque composante est un ensemble de sommets.
    """
    visite = set()
    composantes = []

    def dfs_composante(sommet, composante):
        visite.add(sommet)
        composante.add(sommet)
        for voisin in graphe.voisins(sommet):
            if voisin not in visite:
                dfs_composante(voisin, composante)

    for s in graphe.sommets():
        if s not in visite:
            comp = set()
            dfs_composante(s, comp)
            composantes.append(comp)

    return composantes


# Graphe avec deux composantes connexes
G2 = Graphe(7)
for u, v in [(0, 1), (0, 2), (1, 2), (3, 4), (5, 6)]:
    G2.ajouter_arete(u, v)

comps = composantes_connexes(G2)
print(f"Nombre de composantes connexes : {len(comps)}")
for i, comp in enumerate(comps):
    print(f"  Composante {i + 1} : {sorted(comp)}")

Nombre de composantes connexes : 3
  Composante 1 : [0, 1, 2]
  Composante 2 : [3, 4]
  Composante 3 : [5, 6]

Composantes fortement connexes (introduction à Kosaraju)#

Dans les graphes orientés, la notion de composante connexe se renforce : deux sommets $u$ et $v$ sont fortement connexes s’il existe un chemin de $u$ vers $v$ et un chemin de $v$ vers $u$.

Composante fortement connexe

Une composante fortement connexe (SCC, Strongly Connected Component) d’un graphe orienté est un sous-graphe maximal dans lequel tout sommet est accessible depuis tout autre par un chemin orienté.

L’algorithme de Kosaraju calcule toutes les SCC en deux passes DFS en $O(n + m)$ :

Effectuer un DFS sur le graphe $G$ et enregistrer les sommets par ordre de fin de traitement.
Calculer le graphe transposé $G^T$ (toutes les arêtes inversées).
Effectuer des DFS sur $G^T$ en traitant les sommets dans l’ordre décroissant de fin de traitement de l’étape 1. Chaque arbre DFS construit est une SCC.

def kosaraju(n, adj_orientee):
    """
    Algorithme de Kosaraju pour les SCC d'un graphe orienté.
    adj_orientee : dict {sommet: [voisins]}
    Retourne la liste des SCC.
    """
    # Étape 1 : DFS sur G, ordre de fin de traitement
    visite = set()
    ordre_fin = []

    def dfs1(v):
        visite.add(v)
        for voisin in adj_orientee.get(v, []):
            if voisin not in visite:
                dfs1(voisin)
        ordre_fin.append(v)

    for s in range(n):
        if s not in visite:
            dfs1(s)

    # Étape 2 : construire le graphe transposé
    adj_T = defaultdict(list)
    for u, voisins in adj_orientee.items():
        for v in voisins:
            adj_T[v].append(u)

    # Étape 3 : DFS sur G^T dans l'ordre de fin décroissant
    visite2 = set()
    sccs = []

    def dfs2(v, scc):
        visite2.add(v)
        scc.append(v)
        for voisin in adj_T.get(v, []):
            if voisin not in visite2:
                dfs2(voisin, scc)

    for s in reversed(ordre_fin):
        if s not in visite2:
            scc = []
            dfs2(s, scc)
            sccs.append(scc)

    return sccs


# Exemple : graphe orienté avec plusieurs SCC
adj = {0: [1], 1: [2], 2: [0, 3], 3: [4], 4: [5], 5: [3]}
sccs = kosaraju(6, adj)
print("Composantes fortement connexes :")
for i, scc in enumerate(sccs):
    print(f"  SCC {i + 1} : {sorted(scc)}")

Composantes fortement connexes :
  SCC 1 : [0, 1, 2]
  SCC 2 : [3, 4, 5]

_images/0e74bb42d2a6c26fa1b9bf4e427fd9f530f705a3a5d95eb273eb449f27ef5ec6.png

Implémentation Python complète#

class GrapheOriente:
    """Graphe orienté représenté par une liste d'adjacence."""

    def __init__(self, n_sommets):
        self.n = n_sommets
        self.adj = defaultdict(list)

    def ajouter_arc(self, u, v):
        self.adj[u].append(v)

    def sommets(self):
        return range(self.n)

    def voisins(self, v):
        return self.adj[v]

    def dfs_complet(self, source=None):
        """DFS complet : explore toutes les composantes."""
        visite = set()
        arbre_dfs = {}  # parent dans l'arbre DFS
        ordre = []

        def explorer(v, parent):
            visite.add(v)
            arbre_dfs[v] = parent
            ordre.append(v)
            for voisin in self.voisins(v):
                if voisin not in visite:
                    explorer(voisin, v)

        departs = [source] if source is not None else self.sommets()
        for s in departs:
            if s not in visite:
                explorer(s, None)

        return ordre, arbre_dfs

    def bfs_distances(self, source):
        """BFS depuis source. Retourne les distances à tous les sommets accessibles."""
        dist = {source: 0}
        file = deque([source])
        while file:
            u = file.popleft()
            for v in self.voisins(u):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    file.append(v)
        return dist

    def tri_topologique(self):
        """
        Tri topologique par DFS (pour un DAG). O(n + m).
        Lève ValueError si le graphe contient un cycle.
        """
        couleur = {v: 'blanc' for v in self.sommets()}
        ordre_inv = []

        def dfs(v):
            couleur[v] = 'gris'
            for voisin in self.voisins(v):
                if couleur[voisin] == 'gris':
                    raise ValueError("Cycle détecté : tri topologique impossible")
                if couleur[voisin] == 'blanc':
                    dfs(voisin)
            couleur[v] = 'noir'
            ordre_inv.append(v)

        for s in self.sommets():
            if couleur[s] == 'blanc':
                dfs(s)

        return list(reversed(ordre_inv))


# Démonstration : tri topologique d'un DAG
dag = GrapheOriente(6)
for u, v in [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]:
    dag.ajouter_arc(u, v)

print("Tri topologique du DAG :", dag.tri_topologique())

# Test DFS et BFS
go = GrapheOriente(5)
for u, v in [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]:
    go.ajouter_arc(u, v)

ordre, arbre = go.dfs_complet(0)
print("DFS complet depuis 0 :", ordre)
dist = go.bfs_distances(0)
print("Distances BFS depuis 0 :", dict(sorted(dist.items())))

Tri topologique du DAG : [5, 4, 2, 3, 1, 0]
DFS complet depuis 0 : [0, 1, 3, 4, 2]
Distances BFS depuis 0 : {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

Implémentation Rust#

use std::collections::{HashMap, VecDeque, HashSet};

/// Graphe non orienté représenté par une liste d'adjacence.
struct Graphe {
    n: usize,
    adj: HashMap<usize, Vec<usize>>,
}

impl Graphe {
    fn nouveau(n: usize) -> Self {
        Graphe { n, adj: HashMap::new() }
    }

    fn ajouter_arete(&mut self, u: usize, v: usize) {
        self.adj.entry(u).or_default().push(v);
        self.adj.entry(v).or_default().push(u);
    }

    fn voisins(&self, v: usize) -> &[usize] {
        self.adj.get(&v).map(|vec| vec.as_slice()).unwrap_or(&[])
    }

    /// DFS récursif depuis `depart`. Retourne l'ordre de visite.
    fn dfs(&self, depart: usize) -> Vec<usize> {
        let mut visite = HashSet::new();
        let mut ordre = Vec::new();
        self.dfs_interne(depart, &mut visite, &mut ordre);
        ordre
    }

    fn dfs_interne(
        &self,
        v: usize,
        visite: &mut HashSet<usize>,
        ordre: &mut Vec<usize>,
    ) {
        visite.insert(v);
        ordre.push(v);
        let mut voisins: Vec<usize> = self.voisins(v).to_vec();
        voisins.sort_unstable();
        for voisin in voisins {
            if !visite.contains(&voisin) {
                self.dfs_interne(voisin, visite, ordre);
            }
        }
    }

    /// BFS depuis `depart`. Retourne (ordre, distances).
    fn bfs(&self, depart: usize) -> (Vec<usize>, HashMap<usize, usize>) {
        let mut visite = HashSet::new();
        let mut file = VecDeque::new();
        let mut ordre = Vec::new();
        let mut distances = HashMap::new();

        visite.insert(depart);
        file.push_back(depart);
        distances.insert(depart, 0);

        while let Some(sommet) = file.pop_front() {
            ordre.push(sommet);
            let mut voisins: Vec<usize> = self.voisins(sommet).to_vec();
            voisins.sort_unstable();
            for voisin in voisins {
                if !visite.contains(&voisin) {
                    visite.insert(voisin);
                    distances.insert(voisin, distances[&sommet] + 1);
                    file.push_back(voisin);
                }
            }
        }
        (ordre, distances)
    }

    /// Détection de cycle dans un graphe non orienté via DFS.
    fn contient_cycle(&self) -> bool {
        let mut visite = HashSet::new();

        fn dfs_cycle(
            graphe: &Graphe,
            v: usize,
            parent: Option<usize>,
            visite: &mut HashSet<usize>,
        ) -> bool {
            visite.insert(v);
            for &voisin in graphe.voisins(v) {
                if !visite.contains(&voisin) {
                    if dfs_cycle(graphe, voisin, Some(v), visite) {
                        return true;
                    }
                } else if Some(voisin) != parent {
                    return true; // arête de retour
                }
            }
            false
        }

        for s in 0..self.n {
            if !visite.contains(&s) {
                if dfs_cycle(self, s, None, &mut visite) {
                    return true;
                }
            }
        }
        false
    }
}

fn main() {
    let mut g = Graphe::nouveau(6);
    for (u, v) in [(0,1),(0,2),(1,2),(1,3),(2,4),(3,4),(3,5),(4,5)] {
        g.ajouter_arete(u, v);
    }

    let dfs_ordre = g.dfs(0);
    println!("DFS depuis 0 : {:?}", dfs_ordre);

    let (bfs_ordre, distances) = g.bfs(0);
    println!("BFS depuis 0 : {:?}", bfs_ordre);
    println!("Distances    : {:?}", distances);
    println!("Contient cycle : {}", g.contient_cycle());
}

Résumé#

Ce chapitre a posé les fondements de la théorie des graphes et de ses algorithmes de parcours :

Un graphe $G = (V, E)$ généralise l’arbre en supprimant les contraintes de hiérarchie et d’acyclicité. On distingue graphes orientés et non orientés, simples et multi, pondérés et non pondérés.
Les deux représentations fondamentales sont la matrice d’adjacence ($O(n^2)$ espace, accès en $O(1)$) et la liste d’adjacence ($O(n + m)$ espace, parcours des voisins en $O(\deg)$). La liste d’adjacence est presque toujours préférable pour les graphes creux.
Le DFS explore en profondeur en utilisant la pile (récursive ou explicite). Il permet de détecter les cycles, calculer les composantes connexes et effectuer le tri topologique, le tout en $O(n + m)$.
Le BFS explore niveau par niveau avec une file, et calcule les plus courts chemins (en nombre d’arêtes) en $O(n + m)$.
La détection de cycles dans un graphe orienté repose sur la coloration blanc/gris/noir lors du DFS : une arête vers un sommet gris signale un cycle.
Les composantes fortement connexes d’un graphe orienté se calculent en $O(n + m)$ par l’algorithme de Kosaraju (deux passes DFS).
En Rust, les graphes se représentent naturellement avec HashMap<usize, Vec<usize>>, et les algorithmes DFS/BFS s’expriment de façon idiomatique avec HashSet et VecDeque.

Le chapitre suivant aborde les tables de hachage, une structure qui permet d’associer des clés à des valeurs avec une recherche en $O(1)$ en moyenne, au prix d’une gestion soigneuse des collisions.