Graphes et parcours

Vocabulaire et représentations

Un graphe est formé de sommets (les stations, les routeurs, les modules…) reliés par des arêtes (graphe non orienté : la liaison marche dans les deux sens) ou par des arcs (graphe orienté : la liaison a un sens).

Il y a trois façons usuelles de représenter un graphe en Python.

• Matrice d'adjacence : un tableau M de $n \times n$ cases, où M[i][j] = 1 s'il existe une arête (ou un arc $i \to j$), et 0 sinon.

• Listes de successeurs (ou de voisins) : pour chaque sommet, la liste des sommets atteignables en une étape.

• Listes de prédécesseurs : pour chaque sommet, la liste des sommets qui pointent vers lui (graphes orientés).

Pour le graphe de la figure (ordre A, B, C, D) :

g = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}

Pourquoi ces deux choix ? La matrice permet de tester « $i$ et $j$ sont-ils reliés ? » en un seul accès, mais occupe $n^2$ cases. Les listes n'enregistrent que les liaisons existantes : c'est plus économe quand il y a peu d'arêtes.

Parcours en largeur et en profondeur

Parcourir un graphe, c'est visiter ses sommets un par un, depuis un sommet de départ, sans jamais en visiter un deux fois. Deux stratégies :

• En largeur (BFS) : on visite d'abord tous les voisins du départ, puis les voisins des voisins, etc. On utilise une file (FIFO).

• En profondeur (DFS) : on s'enfonce le plus loin possible, puis on revient en arrière. On utilise une pile (LIFO) ou la récursivité.

Le parcours en largeur explore « par cercles » autour du départ : le premier chemin trouvé vers un sommet est donc de longueur minimale (en nombre d'arêtes).

from collections import deque

def parcours_largeur(g, s):

    visites = [s]

    file = deque([s])

    while file:

        u = file.popleft()

        for v in g[u]:

            if v not in visites:

                visites.append(v)

                file.append(v)

    return visites

def parcours_profondeur(g, s, visites=None):

    if visites is None:

        visites = []

    visites.append(s)

    for v in g[s]:

        if v not in visites:

            parcours_profondeur(g, v, visites)

    return visites

Pour obtenir la distance de s à chaque sommet, on remplace la liste visites par un dictionnaire dist : dist[s] = 0, et lorsqu'on découvre v depuis u, on pose dist[v] = dist[u] + 1.

Détecter un cycle

Un cycle est une « boucle » dans le graphe. Pour en repérer un dans un graphe non orienté, on fait un parcours en profondeur en retenant, pour chaque sommet, son parent (le sommet d'où l'on vient).

Pourquoi ? Ce voisin déjà visité est relié au départ par un chemin du parcours ; l'arête qu'on vient de trouver referme une boucle. Le parent, lui, est toujours déjà visité : l'arête qui y mène est celle qu'on vient de parcourir, elle ne prouve rien.

def a_cycle(g, u, parent, visites):

    visites.add(u)

    for v in g[u]:

        if v not in visites:

            if a_cycle(g, v, u, visites):

                return True

        elif v != parent:

            return True

    return False

Dépendances, interblocage et routage

Les graphes orientés modélisent des dépendances : un arc $X \to Y$ signifie « $X$ avant $Y$ ». Un ordre valide existe seulement si le graphe n'a pas de cycle orienté. Un cycle de dépendances est la même situation qu'un interblocage (deadlock) : chaque processus attend une ressource détenue par le suivant, et personne ne peut avancer. On le détecte en cherchant un cycle par un parcours en profondeur.

Les graphes pondérés (chaque arête porte un coût) modélisent les réseaux. Les routeurs choisissent la route d'un paquet selon un protocole :

• RIP compte le nombre de sauts (routeurs traversés), sans tenir compte du débit ;

• OSPF minimise la somme des coûts des liaisons, c'est-à-dire un plus court chemin dans un graphe pondéré.

L'algorithme de Dijkstra calcule ces plus courts chemins depuis un sommet de départ.

Vers le début : l'application de métro cherche un chemin dans un graphe dont les sommets sont les stations ; en comptant les stations, elle utilise un parcours en largeur, et avec les durées de trajet, un algorithme de type Dijkstra.

L'essentiel

• Un graphe est défini par des sommets et des arêtes (non orienté) ou des arcs (orienté) ; le degré compte les arêtes d'un sommet.

• Représentations : matrice d'adjacence (symétrique si non orienté), listes de successeurs/prédécesseurs ou de voisins (dictionnaire Python).

• Parcours en largeur (file) : sommets par distance croissante, donne un plus court chemin en nombre d'arêtes ; en profondeur (pile ou récursivité). Chaque sommet est visité une fois : coût en $O(n+m)$.

• Un cycle apparaît quand on rencontre un sommet déjà visité qui n'est pas le parent ; un cycle de dépendances rend tout ordre impossible (comme un interblocage).

• RIP minimise le nombre de sauts, OSPF le coût total ; Dijkstra calcule les plus courts chemins dans un graphe pondéré.