Structures de données et graphes

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• expliquer pourquoi le coût d'un programme dépend autant de la structure de données choisie que de l'algorithme, et chiffrer cet écart sur un cas concret;
• comparer tableau, liste chaînée, pile, file, arbre binaire de recherche et table de hachage par le coût de l'accès, de l'insertion et de la suppression, et choisir celle qui correspond à un motif d'accès donné;
• énoncer ce que garantit et ce que ne garantit pas le «$O(1)$ en moyenne» d'une table de hachage;
• définir un graphe, son degré, ses chemins, ses cycles et sa connexité, et choisir entre matrice d'adjacence et listes d'adjacence en calculant la mémoire des deux;
• dérouler un parcours en largeur et un parcours en profondeur sur un graphe donné, et justifier que le parcours en largeur donne les plus courts chemins d'un graphe non pondéré;
• dérouler l'algorithme de Dijkstra sur un graphe pondéré, donner son coût et expliquer pourquoi il exige des poids positifs ou nuls.

Pourquoi la structure décide du coût

Un contrôle d'accès, deux structures, deux mondes

Une salle de travaux pratiques est équipée d'un lecteur de badges. Le fichier des personnes autorisées contient $n=100000$ numéros; chaque matin, $q=50000$ badges sont présentés et le programme doit, pour chacun, répondre «autorisé» ou «refusé». L'algorithme est trivial: pour chaque badge, chercher son numéro dans le fichier. Le coût, lui, ne l'est pas — il dépend entièrement de la manière dont les $100000$ numéros sont rangés.

Première version. Les numéros sont dans un tableau, dans l'ordre où ils ont été saisis. Chercher, c'est parcourir. Quand le numéro est présent, on s'arrête en moyenne au milieu; quand il est absent, on va jusqu'au bout. Prenons le cas favorable où tous les badges sont valides: chaque requête coûte en moyenne $(n+1)/2=50000,5$ comparaisons, et la matinée en coûte

soit deux milliards et demi de comparaisons.

Deuxième version. Les numéros sont triés et l'on cherche par dichotomie, la méthode du chapitre 3. Chaque requête coûte au plus $\lceil {\log }_{2}n\rceil =\lceil 16,61\rceil =17$ comparaisons, soit $50000\times 17=850000$ comparaisons pour la matinée. Le tri initial se paie une fois, pas chaque matin.

Troisième version. Les numéros sont rangés dans une table de hachage. Chaque requête coûte, en moyenne, un petit nombre constant de comparaisons — disons une ou deux. La matinée coûte de l'ordre de $50000$ à $100000$ comparaisons.

Traduisons en temps. Supposons — c'est une hypothèse de travail, pas une mesure, et le chapitre 2 explique pourquoi une telle constante n'a de sens que sur une machine donnée — que la machine effectue $10^8$ comparaisons par seconde. La première version prend $25$ secondes, la deuxième $8,5$ millisecondes, la troisième un demi-millième de seconde. Le rapport entre la première et la troisième est de $50000$: c'est la différence entre une matinée qui bloque le lecteur de badges et une matinée où personne ne remarque qu'un calcul a eu lieu.

Aucun de ces trois programmes n'est «mieux écrit» que les autres. Ils exécutent la même idée. Ce qui change est la structure de données.

Cette séparation est le cœur du chapitre. Le type abstrait «ensemble avec test d'appartenance» admet au moins trois implémentations, et l'écart de coût que nous venons de calculer est entièrement dû à ce choix. Réciproquement, un algorithme n'a pas de coût dans l'absolu: il a un coût une fois qu'on a dit sur quoi il opère.

Tableau et liste chaînée

Le tableau: la mémoire contiguë

La relation (4.1) est une multiplication et une addition: elle ne dépend pas de $n$, ni de $i$, ni de ce que contient le tableau. L'accès à $T[i]$ coûte donc $\Theta (1)$, et c'est la seule structure de ce chapitre pour laquelle l'accès par indice est gratuit. C'est aussi ce qui rend possible la dichotomie du chapitre 3: sauter au milieu d'un tableau trié ne coûte rien, sauter au milieu d'une liste chaînée coûte la moitié de la liste.

Le revers est que la contiguïté doit être maintenue. Insérer une valeur à la position $i$ oblige à décaler d'une case les $n-i$ éléments qui suivent; supprimer l'élément $i$ oblige à décaler les $n-i-1$ suivants dans l'autre sens. Dans le pire cas — insérer en tête — ce sont $n$ déplacements, donc $\Theta (n)$.

Ajouter à la fin est plus subtil. Si le tableau a été alloué avec de la place en réserve, l'ajout est $\Theta (1)$. S'il est plein, il faut allouer un tableau plus grand et tout recopier, ce qui coûte $\Theta (n)$. La stratégie usuelle — celle des list de Python, des ArrayList de Java, des vector de C++ — est de doubler la capacité à chaque saturation. Construire un tableau de $1000$ éléments par ajouts successifs déclenche alors des recopies de $1,2,4,\dots ,512$ éléments, soit $1023$ recopies au total pour $1000$ ajouts: moins de deux recopies par élément, quelle que soit la taille finale. On dit que l'ajout en fin coûte $\Theta (1)$ : une opération isolée peut être chère, mais la moyenne sur une longue suite d'opérations est bornée par une constante.

La liste chaînée: la mémoire dispersée

Les cellules n'ont aucune raison d'être voisines en mémoire: elles sont où l'allocateur les a mises. Il n'existe donc pas de formule analogue à (4.1), et atteindre le $i$-ème élément impose de suivre $i$ adresses: $\Theta (n)$ dans le pire cas.

En échange, une insertion ne déplace rien. Si l'on tient déjà l'adresse de la cellule $c$ après laquelle insérer, créer une cellule et réécrire deux adresses suffit: $\Theta (1)$, indépendamment de la longueur de la liste. Même chose pour la suppression, à condition de tenir l'adresse de la cellule précédente — ce que la version doublement chaînée offre gratuitement.

Cette souplesse se paie en mémoire. Une liste de $10^6$ entiers de $4$ octets stocke $4$ Mo de contenu utile mais dépense, avec un pointeur de $8$ octets par cellule, au moins $12$ octets par cellule, et $16$ après alignement sur la plupart des machines: 16 Mo au lieu de $4$. Le tableau range la même information quatre fois plus compactement — et il la range de façon contiguë, ce qui, sur une machine réelle, favorise les mémoires caches. Nous ne chiffrerons pas cet effet: il dépend du processeur, de la taille des caches et du motif d'accès, et un facteur inventé ici serait une fabrication. Retenez seulement que le facteur constant joue en faveur du tableau et que la notation $O(\cdot )$ ne le voit pas.

Le tableau de coûts

Voici les deux structures mises face à face. $n$ est le nombre d'éléments; «position connue» signifie qu'on tient déjà l'adresse de la cellule ou l'indice concerné.

Pile et file: le même contenu, deux disciplines

Les deux structures suivantes se distinguent non par leur coût — toutes leurs opérations sont $\Theta (1)$ — mais par l'ordre dans lequel elles rendent ce qu'on leur a confié. C'est le premier cas du cours où le choix d'une structure ne change pas la complexité mais le résultat.

Les deux s'implémentent en $\Theta (1)$ par opération. Une pile se réalise avec un tableau et un indice de sommet: empiler écrit à l'indice du sommet puis l'incrémente, dépiler le décrémente puis lit. Une file se réalise avec un tableau circulaire et deux indices, tête et queue, qui avancent modulo la capacité; ou avec une liste chaînée munie d'un pointeur de queue, où enfiler et défiler sont deux réécritures d'adresses. Aucune des deux ne parcourt quoi que ce soit.

Appliquons maintenant la même séquence d'opérations aux deux. Nous ajoutons $3$, puis $7$, puis $5$, retirons une valeur, ajoutons $9$, puis retirons trois fois.

La pile rend $5,9,7,3$: elle restitue les valeurs en ordre inverse d'arrivée, en «déballant» ce qui est au-dessus. La file rend $3,7,5,9$: elle sert dans l'ordre d'arrivée. Le contenu confié est identique, l'ordre rendu ne l'est pas. Retenez cette figure: elle est exactement ce qui distinguera, à la fin du chapitre, le parcours en profondeur du parcours en largeur.

Une pile réelle: la pile d'appels

Le chapitre 3 a montré qu'un appel récursif suspend le calcul en cours, lance un nouveau calcul, et reprend là où il en était. Ce «là où il en était» est stocké dans un bloc d'activation (stack frame): les paramètres de l'appel, ses variables locales et l'adresse de retour. Ces blocs sont empilés, et la discipline est nécessairement LIFO, car un appel ne peut se terminer qu'après tous ceux qu'il a lancés.

C'est pourquoi la profondeur de récursion est une consommation de mémoire, et non un détail. Le tri fusion du chapitre 3 sur $10^6$ éléments descend à une profondeur $\lceil {\log }_{2}10^6\rceil =20$: vingt blocs empilés au maximum — vingt et un si l'on compte le cadre de l'appel initial, comme le fait le chapitre 3 —, rien du tout. Une récursion de profondeur $n$ sur $n=10^6$, en revanche, empile un million de blocs et provoque le () que tout interpréteur signale. La pile n'est pas une métaphore pédagogique: c'est une zone mémoire de taille fixée, et le message d'erreur dit qu'elle est pleine.

Une file réelle: la file d'impression

Une imprimante partagée reçoit des travaux de plusieurs postes et ne peut en traiter qu'un à la fois. Les travaux sont mis en file d'attente et servis dans l'ordre d'arrivée. Le choix du FIFO est ici un choix d'équité, pas d'efficacité: il garantit qu'aucun travail n'attend indéfiniment, ce qu'une pile ne garantirait pas — sous forte charge, un document déposé tôt pourrait rester enfoui sous ceux qui arrivent ensuite et ne jamais sortir. Le même argument vaut pour les files de tâches d'un système d'exploitation, les files de messages entre services, et les tampons de réception du chapitre 10.

Une file sert aussi, sans aucune considération d'équité, à explorer «de proche en proche»: c'est ce que fait le parcours en largeur, et c'est ce qui lui donne sa propriété de plus court chemin.

Arbres et arbres binaires de recherche

Le vocabulaire

Un arbre binaire est un arbre d'arité au plus $2$ dans lequel on distingue, pour chaque nœud, un fils gauche et un fils droit (l'un ou l'autre pouvant manquer). Un arbre à $n$ nœuds a exactement $n-1$ arêtes, puisque chaque nœud sauf la racine apporte l'arête qui le relie à son père.

Démonstration. Montrons d'abord par récurrence sur $d$ que le nombre de nœuds de profondeur $d$ est au plus $2^d$. C'est vrai pour $d=0$: il y a une seule racine. Si les nœuds de profondeur $d$ sont au plus $2^d$ et que chacun a au plus deux fils, les nœuds de profondeur $d+1$, qui sont exactement les fils des précédents, sont au plus . En sommant sur ,

Donc $2^{h+1}\ge n+1$, soit $h+1\ge {\log }_2(n+1)$; comme $h+1$ est entier, .

Cette borne est le plafond de performance de toute méthode qui descend un arbre binaire en faisant un test par niveau: on ne peut pas espérer moins de $\lceil {\log }_2(n+1)\rceil$ tests. Pour $n=7$, elle donne $h\ge 2$; pour $n=10^6$, , donc au moins tests.

L'arbre binaire de recherche

La recherche s'écrit en quatre lignes et n'est rien d'autre que la dichotomie du chapitre 3, exécutée sur une structure au lieu d'un intervalle d'indices:

fonction rechercher(x, clé):
    tant que x n'est pas vide:
        si clé = clé(x): retourner trouvé
        si clé < clé(x): x ← fils gauche de x
        sinon:           x ← fils droit de x
    retourner absent

Chaque tour de boucle descend d'un niveau et fait une comparaison. Le nombre de comparaisons est donc au plus $h+1$, où $h$ est la hauteur. L'insertion suit exactement le même chemin et accroche la nouvelle clé à la place vide où la recherche a échoué.

Tout le coût de l'ABR tient donc dans un seul nombre: sa hauteur. Et la hauteur, elle, dépend de l'ordre d'insertion, pas de l'ensemble des clés.

Un dernier point sur l'ABR: le parcours infixe — visiter le sous-arbre gauche, puis le nœud, puis le sous-arbre droit — rend les clés dans l'ordre croissant, quelle que soit la forme de l'arbre. C'est une conséquence immédiate de la propriété d'ordre, et c'est ce qui fait de l'ABR une structure «triée à tout instant» sans que rien n'ait jamais été trié.

La table de hachage

L'idée

La dichotomie et l'arbre équilibré descendent à ${\log }_{2}n$ comparaisons. La table de hachage vise plus bas: ne pas chercher du tout. Si l'on savait, à partir de la clé seule, calculer directement la case où elle doit se trouver, la recherche coûterait un calcul et une lecture, sans aucune comparaison de parcours.

L'exemple le plus simple est $h(k)=k\mathrm{mod}m$ pour des clés entières. Pour des chaînes de caractères, on combine les codes des caractères par une formule polynomiale; pour des objets, on combine les hachages des champs. La seule exigence de principe est la reproductibilité: la même clé doit toujours donner le même seau.

Les collisions sont inévitables

Il ne s'agit pas d'un défaut de conception que l'on pourrait corriger. Si $|\mathcal{U}|>m$ — et c'est toujours le cas, puisque $\mathcal{U}$ est l'ensemble de tous les entiers de $64$ bits, ou de toutes les chaînes de caractères — alors par le principe des tiroirs, il existe nécessairement deux clés distinctes de même image. Toute table de hachage doit donc prévoir une stratégie de résolution.

La plus lisible est le chaînage séparé (separate chaining): chaque seau contient une liste chaînée, et une clé en collision est simplement ajoutée à la liste de son seau. Chercher $k$ consiste alors à calculer $h(k)$, puis à parcourir la liste du seau $h(k)$ en comparant. L'autre grande famille est l'adressage ouvert (open addressing), où tout est rangé dans le tableau lui-même: en cas de collision, on essaie le seau suivant (sondage linéaire), ou une suite de seaux déterminée par la clé. Nous nous en tenons au chaînage, qui suffit à faire apparaître les coûts.

La figure 4.2 illustre un point que l'intuition refuse: avec seulement six clés dans sept seaux, une collision s'est déjà produite. Ce n'est pas de la malchance. Sous l'hypothèse d'un hachage uniforme — chaque clé tombe dans chacun des $m$ seaux avec probabilité $1/m$, indépendamment des autres — la probabilité qu'aucune des $6$ clés n'entre en collision vaut

de sorte qu'il y a environ $95,7\%$ de chances d'observer au moins une collision. C'est le calcul du «paradoxe des anniversaires»: les collisions apparaissent dès que le nombre de clés est de l'ordre de $\sqrt{m}$, très loin de $m$.

Le coût, et ce qu'il garantit

Une recherche coûte le calcul de $h(k)$, puis le parcours d'une chaîne. Sous l'hypothèse du hachage uniforme, la chaîne visitée contient en moyenne $\alpha$ éléments lorsque la clé est absente, et le résultat classique donne $1+\alpha /2$ comparaisons en moyenne lorsqu'elle est présente. Dans la table de la figure 4.2, $\alpha =6/7\approx 0,857$, donc environ $0,86$ comparaison pour un échec et $1,43$ pour un succès.

Le point décisif est que $\alpha$ ne dépend pas de $n$ seul: il dépend du rapport $n/m$. Si l'on maintient $m$ proportionnel à $n$ — en doublant $m$ et en re-hachant tout dès que $\alpha$ dépasse un seuil, typiquement $0,75$ — alors $\alpha$ reste borné par une constante, et les trois opérations (recherche, insertion, suppression) coûtent $O(1)$ en moyenne. Le re-hachage coûte mais, par le même argument de doublement que pour les tableaux, il s'amortit en par opération.

Le pire cas, lui, est atroce. Si toutes les clés tombent dans le même seau, la table est une liste chaînée de $n$ éléments et chaque recherche coûte $\Theta (n)$.

Notons au passage ce qu'une table de hachage perd par rapport à un arbre: l'ordre. L'ABR rend ses clés triées par un parcours infixe et répond aux requêtes par intervalle («toutes les clés entre $100$ et $200$»); la table de hachage disperse volontairement les clés voisines et ne sait répondre qu'à «cette clé exacte est-elle là». C'est le troisième compromis du chapitre, après temps contre mémoire et moyenne contre garantie: fonctionnalité contre vitesse.

Les graphes

Définitions

Toutes les structures précédentes rangent des valeurs. Un graphe range des relations: ce sont les liens entre les objets qui portent l'information.

Un graphe connexe et sans cycle est un arbre (non enraciné); il vérifie $m=n-1$, et c'est le nombre minimal d'arêtes d'un graphe connexe à $n$ sommets.

Démonstration. Comptons de deux façons les couples $(v,e)$ où $e$ est une arête incidente au sommet $v$. En groupant par sommet, on obtient ${\sum }_v\mathrm{deg}(v)$. En groupant par arête, chaque arête $\{u,v\}$ fournit exactement deux couples, $(u,e)$ et : on obtient . Les deux comptes sont égaux. Comme est pair et que les degrés pairs contribuent une somme paire, la somme des degrés impairs est paire, donc ils sont en nombre pair.

Le graphe à huit sommets que nous utiliserons dans tout ce qui suit a les arêtes $AB,AC,AD,BE,CE,CF,DF,DH,EG,FG,GH$, donc $n=8$ et $m=11$. Ses degrés valent pour : leur somme fait , conformément au théorème 4.2. Il est connexe, et il contient des cycles (par exemple ).

Deux représentations, deux factures

La matrice occupe $n^2$ cases quel que soit le nombre d'arêtes. Les listes occupent $2m$ références (ou $m$ pour un graphe orienté), plus les $n$ têtes de listes. Tout dépend donc de la densité du graphe, c'est-à-dire du rapport $2m/(n(n-1))$ entre le nombre d'arêtes présentes et le nombre d'arêtes possibles.

Le coût mémoire n'est pas le seul critère. Les deux représentations n'offrent pas les mêmes opérations au même prix:

La dernière ligne est celle qui décide dans la plupart des applications: tous les algorithmes de la fin de ce chapitre parcourent le graphe, et ce parcours coûte $\Theta (n^2)$ avec une matrice contre $\Theta (n+m)$ avec des listes. Sur le réseau routier de l'exemple 4.3, c'est $10^8$ contre $25000$ opérations — un facteur $4000$ obtenu sans toucher à une ligne de l'algorithme.

Parcourir un graphe

Un seul algorithme, deux conteneurs

Explorer un graphe depuis un sommet $s$, c'est visiter tous les sommets qu'on peut atteindre, une fois chacun. La difficulté propre aux graphes — absente des arbres — est la présence de cycles: sans précaution, on tourne indéfiniment. Il faut donc marquer les sommets déjà vus.

Le schéma général tient en dix lignes. Un conteneur garde les sommets découverts mais pas encore traités:

parcours(G, s):
    marquer s comme découvert
    mettre s dans le conteneur
    tant que le conteneur n'est pas vide:
        v ← retirer un sommet du conteneur
        visiter v
        pour chaque voisin w de v:
            si w n'est pas découvert:
                marquer w comme découvert
                mettre w dans le conteneur

Deux points de ce code décident de tout le reste, et il faut les lire lentement.

D'abord, un sommet est marqué au moment où on le découvre, c'est-à-dire quand on le met dans le conteneur, et non quand on l'en retire. Un sommet n'entre donc qu'une seule fois dans le conteneur, celui-ci ne contient jamais de doublon, et la boucle fait exactement $n$ retraits. Marquer au retrait plutôt qu'à la découverte donne un algorithme différent — nous y revenons plus bas, car c'est un piège classique.

Ensuite, l'ordre dans lequel on énumère les voisins décide de l'ordre de visite. Nous conviendrons que le plus petit voisin est traité en premier. Pour une file, il suffit d'énumérer les voisins dans l'ordre alphabétique. Pour une pile, le dernier entré étant le premier sorti, il faut les empiler dans l'ordre alphabétique inverse.

Il reste que le code ne dit pas quel sommet retirer. Et c'est là que tout se joue:

• si le conteneur est une file, on retire le plus anciennement découvert: c'est le parcours en largeur (breadth-first search, BFS), qui explore le graphe par couches de distance croissante;
• si le conteneur est une pile, on retire le plus récemment découvert: c'est le parcours en profondeur (depth-first search, DFS), qui s'enfonce le long d'un chemin jusqu'à l'impasse avant de revenir sur ses pas.

Une file au lieu d'une pile, et rien d'autre. La figure 4.1 avait montré que ces deux disciplines rendent des ordres différents; nous allons voir ce que cette différence produit sur un graphe.

Les deux parcours sur le même graphe

Déroulons les deux sur notre graphe à huit sommets, depuis $A$, avec la convention posée plus haut: le plus petit voisin est traité en premier, et un sommet est marqué dès sa découverte (cette convention ne change rien aux propriétés, mais sans elle le résultat n'est pas déterminé). Les traces ci-dessous sont celles que produit l'exécution du schéma, à la ligne près.

Parcours en largeur, avec la file après chaque visite:

L'ordre de visite est $A,B,C,D,E,F,H,G$. On lit dans la colonne de droite la structure en couches: d'abord $A$, puis les trois voisins de $A$, puis les trois sommets à distance $2$, puis $G$ à distance $3$.

Parcours en profondeur, avec la pile après chaque visite (sommet de pile à gauche):

L'ordre de visite est $A,B,E,G,F,H,C,D$. Rien de commun avec le précédent au-delà du premier sommet. Suivez le mécanisme: $A$ dépose $B$, $C$ et $D$ dans la pile, mais seul $B$ est repris aussitôt; $B$ dépose , qui passe devant et ; dépose , qui passe devant à son tour. En quatre étapes le parcours est descendu au fond du graphe, en , le sommet le plus éloigné de — alors que et , voisins immédiats de , attendent au fond de la pile et ne seront servis qu'en dernier. C'est exactement le comportement «plonger d'abord, revenir ensuite», et c'est le contraire de la couche par couche du parcours en largeur.

Les deux parcours coûtent la même chose. Parce qu'un sommet est marqué dès sa découverte, il entre exactement une fois dans le conteneur et en sort exactement une fois: $\Theta (n)$ pour cette partie, sans aucun doublon. Chaque arête $\{u,v\}$ est examinée exactement deux fois, une fois depuis $u$ et une fois depuis $v$, donc $\Theta (m)$ pour l'exploration des listes. Au total $\Theta (n+m)$ avec des listes d'adjacence — et $\Theta (n^2)$ avec une matrice, puisque énumérer les voisins d'un sommet y coûte . Sur notre graphe, chacune des deux exécutions a fait extractions et examens de voisins.

Pourquoi le parcours en largeur donne les plus courts chemins

Notons $\delta (s,v)$ la distance de $s$ à $v$: le nombre minimal d'arêtes d'un chemin de $s$ à $v$, et $+\infty$ si $v$ n'est pas atteignable. Le parcours en largeur, si on lui fait mémoriser $d[w]=d[v]+1$ au moment où il découvre depuis , calcule exactement ces distances.

Démonstration. Établissons d'abord deux propriétés.

(i) $d[v]\ge \delta (s,v)$ pour tout $v$ découvert. Par récurrence sur l'ordre de découverte. On a $d[s]=0=\delta (s,s)$. Si $w$ est découvert depuis $v$, alors $d[w]=d[v]+1\ge \delta (s,v)+1$ par hypothèse de récurrence; or l'arête prolonge un chemin de longueur en un chemin de longueur menant à , donc .

(ii) La file est monotone. À tout instant, si la file contient $x_1,\dots ,x_r$ de la tête vers la queue, alors $d[x_1]\le d[x_2]\le \cdots \le d[x_r]\le d[x_1]+1$. C'est vrai au départ (la file ne contient que ). Un défilement retire et ne peut que resserrer les inégalités. Un enfilement ajoute un avec , où est le sommet en cours de traitement, c'est-à-dire celui qui vient d'être défilé: la file avant l'ajout vérifie , donc ajouter en queue conserve la croissance, et l'écart entre la tête et la queue reste au plus . les sommets sortent de la file par valeurs de non décroissantes.

(iii) $d[v]\le \delta (s,v)$. Par récurrence sur $k=\delta (s,v)$. Pour $k=0$, $v=s$ et $d[s]=0$. Supposons la propriété acquise pour tous les sommets à distance , et soit à distance . Il existe un sommet avec et . Par hypothèse de récurrence , et est défilé à un certain moment. Deux cas. Ou bien n'est pas encore découvert quand est traité: il l'est alors depuis , et . Ou bien a été découvert plus tôt, depuis un sommet défilé avant ; par (ii), , donc .

En combinant (i) et (iii), $d[v]=\delta (s,v)$. Enfin, le chemin obtenu en remontant de $v$ à son découvreur, puis au découvreur de celui-ci, etc., a une longueur égale à $d[v]$ par construction, donc minimale. $\square$

Le point de la preuve est la monotonie (ii): c'est la file, et elle seule, qui garantit que l'on n'atteint jamais un sommet de la couche $k+1$ avant d'avoir épuisé la couche $k$. Remplacez-la par une pile et la conclusion tombe: sur notre graphe, le parcours en profondeur découvre $F$ depuis $G$, donc par le chemin $A,B,E,G,F$ de longueur $4$, et lui attribuerait $d[F]=4$ alors que (le chemin ). Le sommet est logé à la même enseigne. Le parcours en profondeur n'est donc un algorithme de plus court chemin, et l'erreur qu'il commet peut être arbitrairement grande.

Chacun a son domaine. Le parcours en largeur sert aux plus courts chemins non pondérés, au calcul des composantes connexes, et au test de bipartition d'un graphe (colorier les couches alternativement). Le parcours en profondeur sert à la détection de cycles, au tri topologique d'un graphe orienté acyclique — ordonner des tâches soumises à des contraintes de précédence, comme les dépendances entre paquets logiciels —, à la recherche de composantes fortement connexes, et à l'exploration exhaustive d'un espace de solutions, où l'on veut aller au fond d'une branche avant d'en essayer une autre.

Plus courts chemins pondérés: Dijkstra

Le problème change de nature

Quand les arêtes portent des poids — des kilomètres, des minutes, des francs, une probabilité de perte —, le plus court chemin n'est plus celui qui a le moins d'arêtes. Un détour par trois petites arêtes peut battre une grande arête directe, et le parcours en largeur, qui ne compte que les arêtes, donne une réponse fausse.

L'algorithme de Dijkstra (1959) résout ce problème pour des poids positifs ou nuls. Il maintient pour chaque sommet une distance provisoire $d[v]$ — le poids du meilleur chemin connu jusqu'ici, initialisé à $+\infty$ sauf $d[s]=0$ — et un ensemble de sommets définitifs, dont la distance ne bougera plus.

dijkstra(G, w, s):
    d[s] ← 0; d[v] ← +infini pour tout autre v
    définitifs ← ensemble vide
    tant qu'il reste un sommet non définitif de d fini:
        u ← un sommet non définitif de d[u] minimal
        ajouter u aux définitifs
        pour chaque voisin v de u non définitif:
            si d[u] + w(u, v) < d[v]:          # relâchement
                d[v] ← d[u] + w(u, v)
                père[v] ← u

L'opération centrale — comparer $d[u]+w(u,v)$ à $d[v]$ et améliorer si c'est mieux — s'appelle le relâchement de l'arête. Le reste de l'algorithme n'est qu'une règle d'ordre: relâcher les arêtes en partant chaque fois du sommet non définitif le plus proche.

Une exécution complète

Prenons un réseau fictif de six localités $A$ à $F$, les poids étant des distances routières en kilomètres. Les valeurs ci-dessous sont inventées pour l'exemple; elles ne décrivent aucun réseau réel.

Le tableau ci-dessous est celui de l'exécution, sommet par sommet; chaque ligne donne le sommet rendu définitif et l'état du tableau $d$ après les relâchements de cette étape.

Les valeurs en gras sont celles qu'un relâchement a améliorées après avoir déjà été écrites. Suivez $d[D]$: il vaut d'abord $10$ (par $A\to C\to D$, soit $2+8$), puis $8$ (par $A\to C\to B\to D$, soit ). Et vaut (par ) avant de tomber à (par ). Une distance provisoire n'est pas une distance: elle est le meilleur chemin , et elle peut être améliorée tant que le sommet n'est pas définitif.

Les distances finales sont $d[A]=0$, $d[C]=2$, $d[B]=3$, $d[D]=8$, $d[E]=10$, , et le chemin optimal vers est , dont on vérifie le poids: . Remarquez qu'il emprunte arêtes alors que est à trois arêtes de par , dont le poids est . Le plus court chemin pondéré et le plus court chemin en nombre d'arêtes ne coïncident pas.

Notez aussi que les sommets deviennent définitifs par distances croissantes: $0,2,3,8,10,13$. Ce n'est pas un hasard, c'est le cœur de la preuve.

Le coût

Chaque sommet est rendu définitif une fois et chaque arête est relâchée au plus une fois par extrémité, donc $m$ (ou $2m$) relâchements en tout. Reste à extraire le minimum $n$ fois.

• Avec un simple tableau, chaque extraction balaie les $n$ sommets: $\Theta (n^2)$ pour les extractions, $\Theta (m)$ pour les relâchements, soit $\Theta (n^2)$ au total, puisque $m\le n^2$. C'est le bon choix pour un graphe dense.
• Avec une file de priorité implémentée par un tas binaire () — une structure qui rend le minimum et l'insère en —, on obtient . C'est le bon choix pour un graphe creux: sur le réseau routier de l'exemple 4.3, contre .

Là encore, l'algorithme n'a pas changé: c'est la structure choisie pour «prendre le plus petit» qui décide de trois ordres de grandeur.

Pourquoi les poids doivent être positifs ou nuls

Une application: le graphe social

Terminons par un graphe qu'aucune matrice ne peut contenir, et faisons les comptes.

Considérons un réseau social hypothétique de $n=10^9$ comptes où chaque compte a en moyenne $k=200$ liens réciproques. Ces deux nombres sont des hypothèses de travail choisies pour l'ordre de grandeur, pas des chiffres mesurés sur une plateforme réelle. Le nombre d'arêtes est alors $m=nk/2=10^{11}$, et la densité vaut $2m/(n(n-1))\approx 2\cdot 10^{-7}$.

La matrice d'adjacence est impossible. Elle compte $n^2=10^{18}$ cases. Même comprimée à un bit par case, elle occuperait $10^{18}/8=1,25\cdot 10^{17}$ octets, soit 125 pétaoctets — l'ordre de grandeur d'un centre de données entier, pour un graphe dont on a dit qu'il était vide à .

Les listes d'adjacence tiennent. Il faut $2m=2\cdot 10^{11}$ références de $8$ octets, plus $10^9$ têtes de $8$ octets, soit $1,608\cdot 10^{12}$ octets, environ : quelques disques. Le rapport entre les deux représentations est de .

Le parcours suit. Un parcours en largeur complet coûte $\Theta (n+m)\approx 1,01\cdot 10^{11}$ opérations. À l'hypothèse de travail de $10^8$ opérations par seconde et par cœur, cela fait $1010$ secondes, soit environ 17 minutes sur un seul cœur. Le même parcours sur une matrice d'adjacence coûterait $\Theta (n^2)=10^{18}$ opérations, soit secondes: . Le choix de la représentation ne fait pas ici la différence entre lent et rapide; il fait la différence entre faisable et impossible.

Et les distances? Le parcours en largeur donne la distance de n'importe quel compte à n'importe quel autre. De combien de couches a-t-on besoin pour atteindre tout le monde? Majorons: depuis un sommet de degré $k$, la couche $1$ contient au plus $k$ sommets, et chaque sommet d'une couche apporte au plus $k-1$ nouveaux sommets à la suivante. Le nombre de sommets à distance au plus $d$ est donc borné par

Avec $k=200$, cette borne vaut $2,01\cdot 10^2$ pour $d=1$, $4,00\cdot 10^4$ pour $d=2$, pour et pour : elle dépasse le milliard de comptes dès .

Le même appareil décrit d'autres objets. Le web est un graphe orienté dont les sommets sont les pages et les arcs les hyperliens; il est creux (une page porte quelques dizaines de liens, pas des milliards) et il se parcourt par les mêmes algorithmes — un robot d'indexation est littéralement un parcours de graphe, en largeur si l'on veut couvrir un site avant de s'enfoncer, en profondeur sinon. Un réseau de transport est un graphe pondéré dont les poids sont des temps de trajet, et le calculateur d'itinéraires est un Dijkstra — ou l'une de ses variantes accélérées, qui ne changent pas le principe. Un graphe de dépendances entre paquets logiciels est un graphe orienté que l'on trie topologiquement par un parcours en profondeur, et dont un cycle signale une dépendance circulaire impossible à satisfaire.

Synthèse

• Le coût d'un programme dépend autant de la structure de données que de l'algorithme: la même recherche répétée coûte $2,5$ milliards de comparaisons dans un tableau non trié, $850000$ par dichotomie, et quelques dizaines de milliers dans une table de hachage. Choisir une structure, c'est fixer le coût de chaque opération avant d'écrire la première ligne.
• Le tableau donne l'accès par indice en $\Theta (1)$ et paie l'insertion en $\Theta (n)$; la liste chaînée fait exactement l'inverse. Il n'existe pas de meilleure structure, seulement une meilleure adaptation à un motif d'accès — et la bonne question devant un problème est «quelles opérations, combien de fois chacune».
• Pile et file ont les mêmes coûts, toutes leurs opérations étant $\Theta (1)$, mais pas le même ordre de sortie: sur la même séquence, la pile rend $5,9,7,3$ et la file $3,7,5,9$. Cette seule différence sépare la pile d'appels d'une file d'attente, et le parcours en profondeur du parcours en largeur.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, 4e éd., MIT Press, Cambridge, chap. 10 à 12 (structures élémentaires, tables de hachage, arbres de recherche) et 20 à 22 (graphes, parcours, plus courts chemins).
• Sedgewick, R. et Wayne, K., Algorithms, 4e éd., Addison-Wesley, Boston, chap. 1, 3 et 4.
• Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, Boston (le web comme graphe et ce que l'on en déduit).
• Dijkstra, E. W., «A Note on Two Problems in Connexion with Graphs», Numerische Mathematik, vol. 1, 1959, p. 269–271 (l'article original, long de trois pages).
• Sipser, M., Introduction to the Theory of Computation, 3e éd., Cengage, Boston, chap. 0 (le vocabulaire des graphes, énoncé sans détour).
• Polycopiés du cours ICC de l'EPFL, partie «structures de données et graphes».