Graphes et parcours

Vocabulaire des graphes

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

Voici le vocabulaire à connaître, à lire sur ce dessin.

• Deux sommets reliés par une arête sont voisins (A et C le sont).

• Le degré d'un sommet est le nombre d'arêtes qui y aboutissent : C a pour degré 3, D a pour degré 1.

• Dans un graphe orienté, les successeurs de X sont les sommets Y tels que X→Y est un arc ; les prédécesseurs de X sont les sommets W tels que W→X est un arc. On parle de degré sortant et de degré entrant.

• Un chemin est une suite de sommets où deux sommets consécutifs sont reliés (en respectant le sens des arcs dans un graphe orienté). Sa longueur est son nombre d'arêtes (ou d'arcs). Ici, A–C–D est un chemin de longueur 2.

• Un cycle est un chemin qui revient à son point de départ, sans passer deux fois par la même arête. Ici, A–B–C–A est un cycle.

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

Un graphe se décrit aussi en Python par un dictionnaire : à chaque sommet, on associe la liste de ses voisins (ou de ses successeurs). Par exemple {0: [1], 1: [2], 2: [0]} est un graphe orienté avec les arcs 0→1, 1→2, 2→0, c'est-à-dire un cycle de longueur 3.

Représenter un graphe en mémoire

Un programme ne « voit » pas le dessin. Il faut choisir une représentation. Au programme, il y en a deux principales.

La matrice d'adjacence

On numérote les sommets de $0$ à $n-1$. La matrice d'adjacence est un tableau $n \times n$ dont la case de la ligne $i$ et de la colonne $j$ vaut $1$ s'il y a une arête (ou un arc $i \to j$), et $0$ sinon.

Pour le graphe du dessin (ordre A, B, C, D) :

En Python, c'est une liste de listes : m = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]. Alors m[i][j] == 1 teste en une seule opération si $i$ et $j$ sont reliés.

Les listes d'adjacence

Pour chaque sommet, on garde seulement la liste de ses voisins, dans un dictionnaire :

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

Pour un graphe orienté, on stocke les successeurs (parfois aussi les prédécesseurs dans un second dictionnaire).

Voici deux fonctions utiles, qui passent d'une représentation à l'autre :

def degre(matrice, i):

    return sum(matrice[i])

def matrice_vers_listes(m):

    return {i: [j for j in range(len(m)) if m[i][j] == 1]

            for i in range(len(m))}

Parcours en largeur

Un parcours visite tous les sommets accessibles depuis un sommet de départ, chacun une seule fois. Dans le parcours en largeur, on visite d'abord le départ, puis tous ses voisins, puis les voisins de ses voisins, etc. : on avance « cercle par cercle », comme une vague.

Pour cela, il faut se souvenir des sommets à visiter dans l'ordre où on les a découverts : on utilise une file (FIFO, premier entré, premier sorti). On garde aussi l'ensemble des sommets déjà vus, pour ne pas tourner en rond.

from collections import deque

def parcours_largeur(g, s):

    vus = {s}

    file = deque([s])

    ordre = []

    while file:

        u = file.popleft()

        ordre.append(u)

        for v in g[u]:

            if v not in vus:

                vus.add(v)

                file.append(v)

    return ordre

On marque un sommet comme « vu » au moment où on l'ajoute à la file, pas quand on le retire. Ainsi, un sommet n'entre qu'une fois dans la file, donc n'est visité qu'une fois.

Distances et plus court chemin

Le parcours en largeur découvre les sommets par distance croissante au départ. Il suffit de mémoriser, pour chaque sommet, la distance de son découvreur plus 1 :

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

Ici, le dictionnaire dist joue aussi le rôle de l'ensemble des sommets vus. Sur l'exemple précédent, on trouve {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}.

C'est la réponse à la question du début : pour changer le moins possible de ligne, on lance un parcours en largeur depuis la station de départ.

Parcours en profondeur et détection de cycle

Dans le parcours en profondeur, on suit un chemin le plus loin possible. Quand on est bloqué (tous les voisins sont déjà vus), on revient en arrière jusqu'au dernier sommet qui a encore un voisin à explorer. C'est la stratégie du labyrinthe : on s'enfonce, puis on rebrousse chemin.

La version récursive est très courte. La pile des appels de fonction fait le travail de mémorisation :

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

    if vus is None:

        vus = []

    vus.append(s)

    for v in g[s]:

        if v not in vus:

            parcours_profondeur(g, v, vus)

    return vus

Repérer un cycle dans un graphe non orienté

Si, pendant le parcours, on rencontre un sommet déjà visité qui n'est pas le parent du sommet courant, alors on a trouvé un deuxième chemin vers lui : il y a un cycle. On exclut le parent, car l'arête qui nous a fait arriver au sommet courant le relie naturellement à lui.

def a_cycle(g, s, parent, vus):

    vus.add(s)

    for v in g[s]:

        if v not in vus:

            if a_cycle(g, v, s, vus):

                return True

        elif v != parent:

            return True

    return False

# appel : a_cycle(g, depart, None, set())

Pour un graphe non connexe, on relance la fonction depuis chaque sommet non encore vu. Cette fonction suppose qu'il n'y a pas deux arêtes entre les mêmes sommets.

Applications : dépendances et routage

Dépendances et ordre valide

Un graphe orienté modélise souvent des dépendances : l'arc $X \to Y$ signifie que $X$ doit être traité avant $Y$ (un module chargé avant un autre, une tâche avant une autre). Un ordre valide place chaque sommet après tous ses prédécesseurs.

Un tel ordre existe si et seulement si le graphe ne contient aucun cycle : sur un cycle, chaque élément devrait passer avant lui-même.

Ce phénomène ressemble à l'interblocage de deux processus : P1 attend une ressource détenue par P2, qui attend une ressource détenue par P1. En dessinant « qui attend qui » comme un graphe orienté, l'interblocage correspond à un cycle. On le détecte donc par un parcours en profondeur : rencontrer un sommet dont l'exploration n'est pas terminée prouve qu'il y a un cycle.

Routage : RIP et OSPF

Un réseau est un graphe : les routeurs sont les sommets, les liaisons sont les arêtes. Pour acheminer un paquet, chaque routeur doit connaître le meilleur chemin vers sa destination. Deux protocoles de routage s'appuient sur des notions de plus court chemin différentes :

• RIP compte le nombre de sauts (nombre de liaisons) : c'est exactement un parcours en largeur ;

• OSPF associe à chaque liaison un coût (par exemple selon le débit) et cherche le chemin de coût total minimal : c'est un plus court chemin dans un graphe pondéré.

Quand les arêtes ont des poids positifs, le parcours en largeur ne suffit plus. On utilise l'algorithme de Dijkstra : on garde pour chaque sommet la meilleure distance connue depuis le départ, et à chaque étape on fixe définitivement le sommet non fixé de distance minimale, puis on met à jour ses voisins.

L'essentiel