Parcourez un graphe en largeur et en profondeur

Presque tous les algorithmes de ce cours commencent de la même façon : partir d’un sommet et visiter, de proche en proche, tout ce qu’on peut atteindre. Il y a deux manières de le faire, le parcours en largeur et le parcours en profondeur, et chacune répond à des questions différentes.

Notre fil rouge : un petit réseau d’amitiés entre neuf étudiants, notés A à I. Qui est à combien de « poignées de main » de A ? Le groupe forme-t-il un seul bloc ? Y a-t-il une personne dont le départ couperait le groupe en deux ?

Le fil rouge : un réseau d’amitiés

L’amitié est réciproque : le graphe est non orienté. Voici ses arêtes :

A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G, H-I.

On le stocke par listes d’adjacence, chaque liste étant triée par ordre alphabétique (cela fixe l’ordre de visite, et rend les résultats reproductibles) :

amis = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E", "G"],
    "G": ["F"], "H": ["I"], "I": ["H"],
}

Le parcours en largeur (BFS)

L’idée : des cercles concentriques

Le parcours en largeur (breadth-first search, BFS) visite d’abord tous les voisins de la source, puis les voisins des voisins, et ainsi de suite, comme une onde qui s’élargit dans l’eau. Pour respecter cet ordre, il range les sommets à traiter dans une file (premier arrivé, premier servi).

1. Marquer la source $s$, lui donner la distance 0 et la mettre dans la file.
2. Tant que la file n’est pas vide : retirer le sommet $x$ en tête ; pour chaque voisin $y$ non marqué, le marquer, poser $\text{dist}(y) = \text{dist}(x) + 1$, noter que $y$ a été découvert depuis $x$, et ajouter $y$ en fin de file.

Exemple

BFS depuis A :

Étape	Sommet retiré	Voisins découverts	File après l’étape
1	A (distance 0)	B, C (distance 1)	B, C
2	B	D (distance 2)	C, D
3	C	E (distance 2) ; D déjà marqué	D, E
4	D	F (distance 3)	E, F
5	E	aucun (F déjà marqué)	F
6	F	G (distance 4)	G
7	G	aucun	vide

Les distances depuis A sont donc : B et C à 1, D et E à 2, F à 3, G à 4. H et I ne sont jamais atteints.

from collections import deque

def bfs(graphe, source):
    """Distances (en nombre d'arêtes) et parents depuis la source."""
    dist = {source: 0}
    parent = {source: None}
    file = deque([source])
    while file:
        x = file.popleft()                 # on sert le premier arrivé
        for y in graphe[x]:
            if y not in dist:              # y n'a pas encore été découvert
                dist[y] = dist[x] + 1
                parent[y] = x
                file.append(y)
    return dist, parent

dist, parent = bfs(amis, "A")
print(dist)   # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}

Ce que garantit le BFS

Les liens parent forment un arbre : l’arbre du parcours en largeur, enraciné en A. En remontant les parents depuis G (G ← F ← D ← B ← A), on obtient un chemin de longueur minimale en nombre d’arêtes. C’est la propriété clé du BFS : comme on traite les sommets par distance croissante, le premier chemin qui découvre un sommet est forcément l’un des plus courts.

Le BFS avance par couches : les numéros en ambre donnent l'ordre de sortie de la file, et l'arbre des parents (en vert) contient un plus court chemin vers chaque sommet.

À retenir

Le BFS calcule les plus courts chemins en nombre d’arcs depuis une source. Pour des arcs de longueurs différentes (des minutes, des kilomètres), il ne suffit plus : il faudra Dijkstra ou Bellman-Ford (chapitre 7).

Le parcours en profondeur (DFS)

L’idée : aller le plus loin possible, puis revenir

Le parcours en profondeur (depth-first search, DFS) fait l’inverse : il suit un chemin aussi loin que possible, et ne revient en arrière (backtracking) que lorsqu’il est bloqué. C’est la stratégie de l’explorateur de labyrinthe qui garde toujours la main sur le mur. Il utilise une pile, ou tout simplement la récursivité (la pile d’appels joue ce rôle).

On note souvent deux dates pour chaque sommet : sa date de début (quand on le découvre) et sa date de fin (quand tous ses descendants ont été explorés).

Exemple

DFS depuis A, voisins pris par ordre alphabétique : A → B → D (le premier voisin non visité de D est C) → C → E (les voisins de C, A et D, sont déjà visités) → F → G. G n’a plus de voisin libre : on remonte à F, puis E, C, D, B, A, qui n’ont plus rien à explorer. On relance ensuite depuis H, premier sommet non visité, qui atteint I.

Ordre de visite : A, B, D, C, E, F, G, puis H, I. Les dates de début et de fin valent A (1, 14), B (2, 13), D (3, 12), C (4, 11), E (5, 10), F (6, 9), G (7, 8), puis H (15, 18) et I (16, 17).

Le DFS plonge de A à G par B, D, C, E, F ; les arêtes C-A et F-D, qui ramènent vers un ancêtre, restent hors de l'arbre.

Remarquez l’emboîtement des intervalles : celui de G est dans celui de F, lui-même dans celui de E, etc. Un sommet $y$ est un descendant de $x$ dans l’arbre du DFS exactement quand l’intervalle de $y$ est inclus dans celui de $x$. Cette propriété, qui semble anodine, est la base d’algorithmes puissants : détection de circuits et tri topologique (chapitre 4), composantes fortement connexes (chapitre 3).

Les intervalles [début, fin] s'emboîtent comme des parenthèses : y descend de x dans l'arbre exactement quand son intervalle est inclus dans celui de x.

def dfs(graphe):
    """Dates de début et de fin de chaque sommet (parcours complet du graphe)."""
    debut, fin = {}, {}
    horloge = 0

    def explorer(x):
        nonlocal horloge
        horloge += 1
        debut[x] = horloge
        for y in graphe[x]:
            if y not in debut:
                explorer(y)             # on plonge avant de regarder le voisin suivant
        horloge += 1
        fin[x] = horloge

    for x in graphe:                    # relance depuis chaque sommet non visité
        if x not in debut:
            explorer(x)
    return debut, fin

Attention

La version récursive est la plus lisible, mais Python limite la profondeur de récursion (1 000 appels par défaut). Sur un graphe d’un million de sommets en forme de longue chaîne, elle plante. En production, on écrit une version itérative avec une pile explicite.

Complexité des deux parcours

Chaque sommet est marqué une fois, et chaque liste d’adjacence est parcourue une fois. Avec des listes, le coût total est donc en $O(n + m)$ : proportionnel à la taille du graphe, on ne peut pas faire mieux puisqu’il faut au moins lire le graphe. Avec une matrice d’adjacence, trouver les voisins d’un sommet coûte $O(n)$, et le parcours passe à $O(n^2)$.

	BFS	DFS
Structure	file	pile (ou récursion)
Ordre de visite	par distance croissante	le plus loin possible d’abord
Complexité (listes)	$O(n + m)$	$O(n + m)$
Usages typiques	plus courts chemins non valués, degrés de séparation, crawl du web niveau par niveau	détection de circuit, tri topologique, composantes fortement connexes, labyrinthes

En entretien

« BFS utilise une file et visite par distance croissante, donc il donne les plus courts chemins en nombre d’arcs. DFS utilise une pile et plonge le plus loin possible ; ses dates de début et de fin servent à détecter les circuits et à faire un tri topologique. Les deux sont en $O(n + m)$ avec des listes d’adjacence. »

Connexité : combien de blocs ?

Composantes connexes

Un graphe non orienté est connexe s’il existe une chaîne entre toute paire de sommets. Sinon, il se découpe en composantes connexes : des blocs de sommets reliés entre eux, sans aucune arête d’un bloc à l’autre. Formellement, « être relié par une chaîne » est une relation d’équivalence, et les composantes sont ses classes.

Trouver les composantes est une application directe des parcours : on lance un BFS (ou un DFS) depuis un sommet non visité, tout ce qu’il atteint forme une composante, et on recommence tant qu’il reste des sommets. Notre réseau a deux composantes : $\lbrace A, B, C, D, E, F, G \rbrace$ et $\lbrace H, I \rbrace$.

def composantes(graphe):
    vu, blocs = set(), []
    for s in graphe:
        if s not in vu:
            dist, _ = bfs(graphe, s)       # tout ce qui est atteignable depuis s
            vu |= set(dist)
            blocs.append(sorted(dist))
    return blocs

print(composantes(amis))   # [['A', 'B', 'C', 'D', 'E', 'F', 'G'], ['H', 'I']]

Points faibles : points d’articulation et isthmes

Dans un réseau (de personnes, de routeurs, de routes), on veut souvent savoir où il est fragile.

• Un point d’articulation est un sommet dont la suppression augmente le nombre de composantes connexes. Dans notre réseau, c’est F : sans lui, G se retrouve isolé.
• Un isthme (ou pont, bridge) est une arête dont la suppression augmente le nombre de composantes. Ici, F-G et H-I sont des isthmes. En revanche, A-B n’en est pas un : si on la retire, A reste relié à B par A-C-D-B.

Une arête est un isthme si et seulement si elle n’appartient à aucun cycle. Un graphe connexe sans point d’articulation (et d’au moins trois sommets) est dit 2-connexe : on peut y retirer n’importe quel sommet sans le déconnecter. Un résultat classique, qui tombait en devoir surveillé, caractérise ces graphes : un graphe connexe sans boucle est 2-connexe si et seulement si deux arêtes adjacentes sont toujours sur un même cycle élémentaire.

Piège

Ne confondez pas les deux notions. Un sommet peut être un point d’articulation sans qu’aucune de ses arêtes ne soit un isthme : pensez à deux triangles qui partagent un seul sommet (deux « nœuds papillon »). Ce sommet commun est un point d’articulation, mais toutes les arêtes sont sur un cycle.

F est un point d'articulation et F-G, H-I sont des isthmes. Le nœud papillon, à droite, a un point d'articulation mais aucun isthme.

La méthode naïve (retirer chaque sommet et relancer un parcours) coûte $O(n(n + m))$. L’algorithme de Hopcroft et Tarjan trouve tous les points d’articulation en un seul DFS, en $O(n + m)$, grâce aux dates de début : c’est un complément classique que networkx implémente.

import networkx as nx

G = nx.Graph([("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"),
              ("D", "F"), ("E", "F"), ("F", "G"), ("H", "I")])
print(nx.shortest_path_length(G, "A"))          # distances BFS depuis A
print(list(nx.dfs_preorder_nodes(G, "A")))      # ordre de visite du DFS
print(list(nx.connected_components(G)))         # deux composantes
print(list(nx.articulation_points(G)))          # ['F']
print(list(nx.bridges(G)))                      # isthmes F-G et H-I

En résumé

• Le parcours en largeur (BFS) utilise une file et visite les sommets par distance croissante : il donne les plus courts chemins en nombre d’arcs.
• Le parcours en profondeur (DFS) utilise une pile ou la récursion ; ses dates de début et de fin s’emboîtent et servent de base à de nombreux algorithmes.
• Les deux parcours coûtent $O(n + m)$ avec des listes d’adjacence, $O(n^2)$ avec une matrice.
• Un graphe non orienté se découpe en composantes connexes, qu’on trouve en relançant un parcours depuis chaque sommet non visité.
• Un point d’articulation (sommet) ou un isthme (arête) est un élément dont la suppression déconnecte le graphe ; un graphe 2-connexe n’a pas de point d’articulation.

Exercices

Exercice · Dérouler un BFS

facile

Déroulez un BFS depuis G sur le réseau d’amitiés (voisins par ordre alphabétique). Donnez l’ordre de visite, la distance de chaque sommet atteint et l’arbre des parents. Quel est le plus court chemin de G à A ?

Voir la solution

• On retire G (distance 0) : on découvre F (distance 1).
• On retire F : on découvre D et E (distance 2), G est déjà marqué.
• On retire D : on découvre B et C (distance 3).
• On retire E : ses voisins C et F sont déjà marqués.
• On retire B : on découvre A (distance 4).
• On retire C, puis A : plus rien de nouveau.

Ordre de visite : G, F, D, E, B, C, A. Parents : F ← G, D ← F, E ← F, B ← D, C ← D, A ← B. En remontant depuis A : A ← B ← D ← F ← G, donc le plus court chemin G, F, D, B, A a 4 arêtes. (Le chemin G, F, D, C, A a la même longueur : les plus courts chemins ne sont pas uniques, le BFS en choisit un selon l’ordre des listes.)

En code

Python

from collections import deque

amis = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"], "D": ["B", "C", "F"],
        "E": ["C", "F"], "F": ["D", "E", "G"], "G": ["F"], "H": ["I"], "I": ["H"]}

def bfs(graphe, source):
    ordre, dist, parent = [], {source: 0}, {source: None}
    file = deque([source])
    while file:
        x = file.popleft()
        ordre.append(x)
        for y in graphe[x]:
            if y not in dist:                 # y découvert pour la première fois
                dist[y], parent[y] = dist[x] + 1, x
                file.append(y)
    return ordre, dist, parent

ordre, dist, parent = bfs(amis, "G")
print(ordre)    # ['G', 'F', 'D', 'E', 'B', 'C', 'A']
print(dist)     # {'G': 0, 'F': 1, 'D': 2, 'E': 2, 'B': 3, 'C': 3, 'A': 4}
chemin, x = [], "A"
while x is not None:                          # on remonte les parents depuis A
    chemin.append(x)
    x = parent[x]
print(chemin[::-1])   # ['G', 'F', 'D', 'B', 'A']

R

amis <- list(A = c("B", "C"), B = c("A", "D"), C = c("A", "D", "E"), D = c("B", "C", "F"),
             E = c("C", "F"), F = c("D", "E", "G"), G = "F", H = "I", I = "H")

bfs <- function(graphe, source) {
  dist <- c(); dist[source] <- 0
  parent <- c(); parent[source] <- NA
  file <- source; ordre <- c()
  while (length(file) > 0) {
    x <- file[1]; file <- file[-1]            # on sert le premier de la file
    ordre <- c(ordre, x)
    for (y in graphe[[x]]) if (is.na(dist[y])) {
      dist[y] <- dist[x] + 1; parent[y] <- x; file <- c(file, y)
    }
  }
  list(ordre = ordre, dist = dist, parent = parent)
}

res <- bfs(amis, "G")
res$ordre      # "G" "F" "D" "E" "B" "C" "A"
res$dist       # G 0, F 1, D 2, E 2, B 3, C 3, A 4
chemin <- c(); x <- "A"
while (!is.na(x)) { chemin <- c(x, chemin); x <- res$parent[[x]] }
chemin         # "G" "F" "D" "B" "A"

Exercice · Trouver les isthmes

moyen

On ajoute l’arête G-H au réseau d’amitiés. Combien y a-t-il de composantes connexes ? Quels sont maintenant les isthmes et les points d’articulation ?

Voir la solution

Avec G-H, tout le monde est relié : une seule composante connexe.

Les arêtes A-B, A-C, B-D et C-D (cycle A, B, D, C), puis C-E, D-F et E-F (cycle C, D, F, E) sont sur des cycles, donc ce ne sont pas des isthmes. Les arêtes F-G, G-H et H-I ne sont sur aucun cycle : ce sont les trois isthmes.

Points d’articulation : F (le retirer isole G, H, I), G (le retirer sépare H et I du reste) et H (le retirer isole I). I et les sommets du bloc de gauche n’en sont pas.

En code

Python

aretes = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"),
          ("D", "F"), ("E", "F"), ("F", "G"), ("H", "I"), ("G", "H")]   # avec G-H
sommets = sorted({x for a in aretes for x in a})

def nb_composantes(sommets, aretes):
    voisins = {x: [] for x in sommets}
    for u, v in aretes:
        voisins[u].append(v)
        voisins[v].append(u)
    vu, nb = set(), 0
    for s in sommets:
        if s not in vu:                       # nouveau bloc : on le parcourt en entier
            nb += 1
            vu.add(s)
            pile = [s]
            while pile:
                for y in voisins[pile.pop()]:
                    if y not in vu:
                        vu.add(y)
                        pile.append(y)
    return nb

base = nb_composantes(sommets, aretes)
isthmes = [a for a in aretes if nb_composantes(sommets, [b for b in aretes if b != a]) > base]
points = [x for x in sommets
          if nb_composantes([s for s in sommets if s != x], [a for a in aretes if x not in a]) > base]
print(base, isthmes, points)   # 1 [('F', 'G'), ('H', 'I'), ('G', 'H')] ['F', 'G', 'H']

R

aretes <- rbind(c("A", "B"), c("A", "C"), c("B", "D"), c("C", "D"), c("C", "E"),
                c("D", "F"), c("E", "F"), c("F", "G"), c("H", "I"), c("G", "H"))
sommets <- sort(unique(as.vector(aretes)))

nb_composantes <- function(sommets, aretes) {
  bloc <- setNames(seq_along(sommets), sommets)   # chaque sommet seul dans son bloc
  for (k in seq_len(nrow(aretes))) {              # une arête fusionne deux blocs
    a <- bloc[aretes[k, 1]]; b <- bloc[aretes[k, 2]]
    bloc[bloc == b] <- a
  }
  length(unique(bloc))
}

base <- nb_composantes(sommets, aretes)
isthme <- sapply(1:nrow(aretes), function(k)
  nb_composantes(sommets, aretes[-k, , drop = FALSE]) > base)
articulation <- sapply(sommets, function(x) {
  garder <- aretes[, 1] != x & aretes[, 2] != x
  nb_composantes(setdiff(sommets, x), aretes[garder, , drop = FALSE]) > base
})
base                                        # 1
apply(aretes[isthme, ], 1, paste, collapse = "-")   # "F-G" "H-I" "G-H"
sommets[articulation]                       # "F" "G" "H"

Exercice · Un parcours pour un labyrinthe

difficile

Un labyrinthe est donné par une grille de 1 000 × 1 000 cases, chaque case étant libre ou murée. On se déplace d’une case libre à une case libre voisine (haut, bas, gauche, droite).

1. Modélisez le problème par un graphe : que sont les sommets, les arêtes ? Majorez $n$ et $m$.
2. Quel parcours choisir pour trouver le chemin le plus court de l’entrée à la sortie ? Quelle est sa complexité ?
3. Faut-il construire explicitement les listes d’adjacence ?

Voir la solution

1. Les sommets sont les cases libres, les arêtes relient deux cases libres voisines. On a $n \leq 10^6$ et, chaque case ayant au plus 4 voisines, $m \leq 4n / 2 = 2 \times 10^6$ arêtes. Le graphe est très creux.
2. Un BFS depuis l’entrée : toutes les arêtes ont la même longueur (un pas), donc le BFS donne le plus court chemin en nombre de pas. Sa complexité est $O(n + m)$, soit quelques millions d’opérations : instantané. Un DFS trouverait un chemin, mais pas forcément le plus court, et sa version récursive dépasserait la limite de récursion de Python.
3. Non : les voisins d’une case $(i, j)$ se calculent à la volée ($(i \pm 1, j)$ et $(i, j \pm 1)$, s’ils sont libres et dans la grille). C’est un graphe implicite, très fréquent en pratique (jeux, images, planification) : on ne stocke que la grille et le tableau des distances.

En code

Python

from collections import deque

grille = ["E..#....",                     # E : entrée, S : sortie, # : mur
          ".#.#.##.",
          ".#...#..",
          ".####.#.",
          "......#S"]

def plus_court(grille):
    h, l = len(grille), len(grille[0])
    depart = next((i, j) for i in range(h) for j in range(l) if grille[i][j] == "E")
    dist = {depart: 0}
    file = deque([depart])
    while file:
        i, j = file.popleft()
        if grille[i][j] == "S":
            return dist[i, j]
        for a, b in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:   # voisins calculés à la volée
            if 0 <= a < h and 0 <= b < l and grille[a][b] != "#" and (a, b) not in dist:
                dist[a, b] = dist[i, j] + 1
                file.append((a, b))
    return None                              # sortie inaccessible

print(plus_court(grille))   # 15 pas

R

grille <- do.call(rbind, strsplit(c("E..#....",   # E : entrée, S : sortie, # : mur
                                    ".#.#.##.",
                                    ".#...#..",
                                    ".####.#.",
                                    "......#S"), ""))

plus_court <- function(grille) {
  dist <- matrix(NA, nrow(grille), ncol(grille))
  depart <- which(grille == "E", arr.ind = TRUE)
  dist[depart] <- 0
  file <- depart                                # file de cases (une ligne par case)
  while (nrow(file) > 0) {
    i <- file[1, 1]; j <- file[1, 2]; file <- file[-1, , drop = FALSE]
    if (grille[i, j] == "S") return(dist[i, j])
    voisins <- rbind(c(i - 1, j), c(i + 1, j), c(i, j - 1), c(i, j + 1))   # calculés à la volée
    for (k in 1:4) {
      a <- voisins[k, 1]; b <- voisins[k, 2]
      if (a >= 1 && a <= nrow(grille) && b >= 1 && b <= ncol(grille) &&
          grille[a, b] != "#" && is.na(dist[a, b])) {
        dist[a, b] <- dist[i, j] + 1
        file <- rbind(file, c(a, b))
      }
    }
  }
  NA                                            # sortie inaccessible
}

plus_court(grille)   # 15 pas