Graphes et parcours

Vocabulaire et représentations

Un graphe sert à modéliser des objets (les sommets) et des liens entre eux : stations et lignes de métro, routeurs et câbles, élèves et amitiés, modules d'un programme et dépendances.

Voici un graphe non orienté à 5 sommets.

Quelques mots à connaître :

• deux sommets reliés par une arête sont voisins (ou adjacents) ;

• le degré d'un sommet est le nombre d'arêtes qui y aboutissent : ici, le sommet 1 a pour degré 3 ;

• un chemin est une suite de sommets où chacun est relié au suivant ; sa longueur est le nombre d'arêtes (ou d'arcs) parcourus : $0 - 1 - 3 - 4$ est un chemin de longueur 3 ;

• un cycle est un chemin qui revient à son point de départ (sans réutiliser une même arête, ou un même arc) ;

• un graphe non orienté est connexe si l'on peut aller de n'importe quel sommet à n'importe quel autre.

Comment représenter un graphe en machine ?

Il existe deux représentations classiques.

La matrice d'adjacence. Pour $n$ sommets numérotés de $0$ à $n-1$, c'est un tableau $n \times n$ où M[i][j] = 1 s'il existe une arête (ou un arc) de $i$ vers $j$, et 0 sinon.

Les listes d'adjacence (ou listes de successeurs). Pour chaque sommet, on mémorise la liste de ses voisins (ses successeurs dans un graphe orienté). En Python, on utilise un dictionnaire : la clef est le sommet, la valeur est la liste des voisins.

Pour le graphe ci-dessus :

M = [[0, 1, 0, 0, 0],

     [1, 0, 1, 1, 0],

     [0, 1, 0, 0, 0],

     [0, 1, 0, 0, 1],

     [0, 0, 0, 1, 0]]

g = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1, 4], 4: [3]}

Parcours en largeur

Parcourir un graphe, c'est visiter ses sommets un par un, chacun une seule fois, en suivant les liaisons à partir d'un sommet de départ. Le parcours en largeur (BFS, breadth-first search) visite d'abord tous les voisins du départ, puis les voisins des voisins, etc. : on avance « par couches », comme une onde qui s'étend.

Pour savoir quel sommet traiter ensuite, on utilise une file (structure FIFO : premier entré, premier sorti). On y met les sommets découverts, et on les traite dans l'ordre de leur découverte.

from collections import deque

def parcours_largeur(g, s):

    vus = [s]

    file = deque([s])

    while file:

        u = file.popleft()

        for v in g[u]:

            if v not in vus:

                vus.append(v)

                file.append(v)

    return vus

On utilise deque car popleft() est une opération rapide ; liste.pop(0) oblige à décaler tous les éléments.

Distances et plus courts chemins

Comme on visite les sommets par couches, le parcours en largeur découvre chaque sommet par un chemin comptant le moins d'arêtes possible. Il suffit de mémoriser la distance de chaque sommet au départ : celle de $v$ est celle de $u$ plus 1, où $u$ est le sommet qui a permis de découvrir $v$.

def distances(g, s):

    dist = {s: 0}

    file = deque([s])

    while file:

        u = file.popleft()

        for v in g[u]:

            if v not in dist:

                dist[v] = dist[u] + 1

                file.append(v)

    return dist

Sur l'exemple : {S: 0, A: 1, B: 1, C: 2, D: 3}. Pour retrouver le chemin lui-même, on mémorise aussi le sommet « parent » de chaque sommet découvert.

Parcours en profondeur et cycles

Le parcours en profondeur (DFS, depth-first search) fait l'inverse : on s'enfonce le plus loin possible dans une direction, et on ne revient en arrière que lorsqu'on est dans une impasse. C'est le principe du labyrinthe avec un fil d'Ariane.

Il utilise une pile (LIFO), le plus souvent de façon implicite grâce à la récursivité.

def parcours_profondeur(g, u, vus=None):

    if vus is None:

        vus = []

    vus.append(u)

    for v in g[u]:

        if v not in vus:

            parcours_profondeur(g, v, vus)

    return vus

Détecter un cycle dans un graphe non orienté

Si pendant le parcours en profondeur on rencontre un sommet déjà visité qui n'est pas le parent du sommet courant, c'est qu'on a trouvé un second chemin vers ce sommet : il y a un cycle. On exclut le parent, car l'arête qu'on vient d'emprunter mène forcément vers lui.

def a_un_cycle(g, u, parent, vus):

    vus.add(u)

    for v in g[u]:

        if v not in vus:

            if a_un_cycle(g, v, u, vus):

                return True

        elif v != parent:

            return True

    return False

On l'appelle avec a_un_cycle(g, s, None, set()) pour la composante connexe de s. Pour un graphe non connexe, on relance depuis chaque sommet non visité.

Graphes orientés : dépendances et interblocage

Dans un graphe orienté, un arc $X \to Y$ peut signifier « $X$ doit être fait avant $Y$ » (chargement de modules, étapes d'une recette, prérequis de cours). Un ordre valide place chaque sommet avant tous ses successeurs. Un tel ordre existe si et seulement si le graphe ne contient aucun cycle orienté.

Cette situation ressemble à un interblocage (deadlock) entre processus : le processus P1 attend une ressource détenue par P2, P2 attend P3, et P3 attend P1. Aucun ne peut avancer. Un graphe d'attente (arc $P_i \to P_j$ : « $P_i$ attend $P_j$ ») avec un cycle orienté signale un interblocage. Détecter le problème revient donc à chercher un cycle par un parcours en profondeur : dans un graphe orienté, on a un cycle si l'on retombe sur un sommet qui est encore « en cours de visite », c'est-à-dire sur le chemin courant.

Graphes pondérés, routage et algorithme de Dijkstra

Dans un réseau, toutes les liaisons ne se valent pas : une fibre rapide n'a pas le même « prix » qu'une vieille liaison lente. On associe alors à chaque arête un nombre, son poids (ou coût) : on obtient un graphe pondéré. Le coût d'un chemin est la somme des poids de ses arêtes.

Les protocoles de routage permettent aux routeurs de choisir la route d'un paquet :

• RIP compte le nombre de sauts (c'est un parcours en largeur : tous les poids valent 1) ;

• OSPF minimise le coût total des liaisons.

Le parcours en largeur ne suffit plus pour OSPF : le chemin avec le moins d'arêtes n'est pas forcément le moins coûteux. On utilise l'algorithme de Dijkstra (poids positifs).

Le chemin $A - B - C - D$ compte 3 sauts. Les chemins $A - B - D$ (coût 8) et $A - C - D$ (coût 7) n'en comptent que 2 : RIP en choisirait un, alors qu'OSPF préfère la route de coût 5.

Reviens au début : l'application de transports modélise le réseau par un graphe (stations = sommets, tronçons = arêtes). Elle cherche le trajet avec le moins de lignes par un parcours en largeur, et le trajet le plus rapide par Dijkstra, en pondérant chaque tronçon par sa durée.

L'essentiel

• Un graphe est formé de sommets reliés par des arêtes (non orienté) ou des arcs (orienté). On parle de degré, de chemin, de longueur et de cycle.

• On le représente par une matrice d'adjacence (tableau $n \times n$, symétrique si le graphe est non orienté) ou par des listes d'adjacence, par exemple un dictionnaire Python.

• Le parcours en largeur utilise une file : il explore par couches et donne les distances minimales en nombre d'arêtes.

• Le parcours en profondeur utilise une pile (ou la récursivité) : il sert à détecter un cycle (sommet déjà visité qui n'est pas le parent) et à vérifier qu'un ordre de dépendances existe.

• Un graphe pondéré se traite avec l'algorithme de Dijkstra : RIP compte les sauts, OSPF minimise le coût.