Les graphes

Considérons quatre personnes : Alice, Bob, Chloé et David. Alice est amie avec Bob et Chloé ; Bob est ami avec Chloé ; Chloé est amie avec David. On modélise cette situation par un graphe non orienté à 4 sommets $\{\text{Alice},\text{Bob},\text{Chloeˊ},\text{David}\}$ et 4 arêtes : \{Alice, Bob\}, \{Alice, Chloé\}, \{Bob, Chloé\} et \{Chloé, David\}. La relation « être ami avec » est symétrique, ce qui justifie l'emploi d'un graphe non orienté.

Les pages d'un site web forment un graphe orienté : chaque page est un sommet, et un lien hypertexte de la page $A$ vers la page $B$ est un arc $(A,B)$. Le fait que $A$ pointe vers $B$ n'implique pas que $B$ pointe vers $A$ : la relation n'est pas symétrique, d'où l'utilisation d'un graphe orienté.

Une carte routière est un graphe pondéré : les villes sont les sommets, les routes sont les arêtes, et le poids d'une arête est la longueur (en kilomètres) de la route correspondante. Calculer le plus court trajet entre deux villes revient à chercher un chemin de poids minimal dans ce graphe.

Dans un graphe non orienté à $m$ arêtes, la somme des degrés de tous les sommets vaut le double du nombre d'arêtes :

$$\sum _{u\in S}\mathrm{deg}(u)=2m.$$

En effet, chaque arête $\{u,v\}$ contribue pour $1$ au degré de $u$ et pour $1$ au degré de $v$, donc pour $2$ au total. On en déduit que le nombre de sommets de degré impair est toujours pair.

Reprenons le réseau d'amitié précédent. La suite Alice, Bob, Chloé, David est un chemin simple de longueur 3 reliant Alice à David. La suite Alice, Bob, Chloé, Alice est un cycle de longueur 3 : on part d'Alice et on y revient. Ce graphe contient donc au moins un cycle, il n'est pas acyclique.

Voici un petit graphe non orienté à 4 sommets ($0,1,2,3$) et aux arêtes $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ et $\{2,3\}$, représenté par sa matrice d'adjacence sous forme de liste de listes en Python.

# Matrice d'adjacence d'un graphe non oriente a 4 sommets
M = [
    [0, 1, 1, 0],   # voisins du sommet 0 : 1 et 2
    [1, 0, 1, 0],   # voisins du sommet 1 : 0 et 2
    [1, 1, 0, 1],   # voisins du sommet 2 : 0, 1 et 3
    [0, 0, 1, 0],   # voisins du sommet 3 : 2
]

# Existe-t-il une arete entre 0 et 2 ?
print(M[0][2] == 1)   # True

# Degre du sommet 2 (somme de sa ligne)
print(sum(M[2]))      # 3

La matrice d'adjacence occupe un espace mémoire de $O(n^2)$, quel que soit le nombre d'arêtes. Tester l'existence d'un lien entre deux sommets se fait en $O(1)$, mais parcourir tous les voisins d'un sommet coûte $O(n)$. Cette représentation est efficace pour les graphes denses (beaucoup d'arêtes), mais gaspilleuse pour les graphes creux (peu d'arêtes).

Reprenons le même graphe que précédemment avec un dictionnaire.

# Listes d'adjacence d'un graphe non oriente
G = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2],
}

# Voisins du sommet 2
print(G[2])           # [0, 1, 3]

# Degre du sommet 2
print(len(G[2]))      # 3

# Existe-t-il une arete entre 0 et 3 ?
print(3 in G[0])      # False

Les listes d'adjacence occupent un espace de $O(n+m)$, proportionnel au nombre de sommets et de liens. Parcourir tous les voisins d'un sommet $u$ coûte $O(\mathrm{deg}(u))$, ce qui est optimal. En revanche, tester l'existence d'un lien précis entre deux sommets coûte $O(\mathrm{deg}(u))$ (parcours de la liste). Cette représentation est privilégiée pour les graphes creux, qui sont les plus fréquents en pratique.

from collections import deque

def bfs(G, depart):
    """Parcours en largeur ; renvoie la liste des sommets dans
    l'ordre de visite."""
    visites = {depart}
    file = deque([depart])
    ordre = []
    while file:
        u = file.popleft()       # retrait en tete (FIFO)
        ordre.append(u)
        for v in G[u]:
            if v not in visites:
                visites.add(v)
                file.append(v)   # ajout en queue
    return ordre

G = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
print(bfs(G, 0))   # [0, 1, 2, 3]

Avec une représentation par listes d'adjacence, le BFS visite chaque sommet une fois et chaque lien une fois, d'où une complexité en temps de $O(n+m)$.

Propriété essentielle : dans un graphe non pondéré, le BFS calcule le plus court chemin (en nombre de liens) du sommet de départ vers tous les autres sommets. C'est pourquoi le BFS est à la base du calcul de distances dans les réseaux sociaux (« degrés de séparation »).

def dfs(G, depart):
    """Parcours en profondeur recursif."""
    visites = set()
    ordre = []

    def explorer(u):
        visites.add(u)
        ordre.append(u)
        for v in G[u]:
            if v not in visites:
                explorer(v)

    explorer(depart)
    return ordre

G = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
print(dfs(G, 0))   # [0, 1, 2, 3]

On peut éviter la récursion en gérant explicitement une pile, ce qui évite tout risque de dépassement de la profondeur de récursion sur les très grands graphes.

def dfs_iteratif(G, depart):
    visites = set()
    ordre = []
    pile = [depart]
    while pile:
        u = pile.pop()            # retrait au sommet (LIFO)
        if u not in visites:
            visites.add(u)
            ordre.append(u)
            for v in G[u]:
                if v not in visites:
                    pile.append(v)
    return ordre

Comme le BFS, le DFS visite chaque sommet et chaque lien une seule fois, sa complexité en temps est donc $O(n+m)$ avec des listes d'adjacence. La différence entre BFS et DFS n'est pas la complexité mais l'ordre de visite : largeur (par couches) contre profondeur (en s'enfonçant). Le choix dépend de l'usage : BFS pour les plus courts chemins non pondérés, DFS pour la détection de cycle, le tri topologique ou l'exploration exhaustive.

Les deux algorithmes reposent sur un DFS et examinent chaque sommet et chaque lien une fois : leur complexité est donc $O(n+m)$. La détection s'arrête dès qu'un cycle est trouvé, ce qui peut être plus rapide en pratique.

Dans un réseau social, les utilisateurs sont les sommets et les relations d'amitié (ou d'abonnement) sont les liens. Un BFS depuis un utilisateur donne sa distance à tous les autres : c'est la notion de degrés de séparation. La célèbre théorie des « six degrés de séparation » affirme que deux personnes quelconques sont reliées par une chaîne d'au plus six relations. Les suggestions d'amis (« personnes que vous connaissez peut-être ») exploitent souvent les sommets à distance 2, c'est-à-dire les amis d'amis.

Dans un réseau informatique, les routeurs sont les sommets et les liaisons physiques les arêtes, pondérées par un coût (latence, bande passante). Acheminer un paquet d'une machine à une autre revient à trouver un chemin dans ce graphe. Sur un réseau non pondéré, le BFS suffit à trouver la route empruntant le moins de sauts ; sur un réseau pondéré, on emploie des algorithmes de plus court chemin pondéré comme celui de Dijkstra, qui généralisent le BFS.