Tableaux et listes, piles et files, arbres et tables de hachage, graphes, parcours en largeur et en profondeur, plus courts chemins.
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 numéros sont rangés.
100000
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
q⋅2n+1=50000×50000,5=2500025000,
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 ⌈log2n⌉=⌈16,61⌉=17 comparaisons, soit 50000×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 108 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 Θ(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 Θ(n).
Ajouter à la fin est plus subtil. Si le tableau a été alloué avec de la place en réserve, l'ajout est Θ(1). S'il est plein, il faut allouer un tableau plus grand et tout recopier, ce qui coûte Θ(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,…,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 Θ(1)amorti: 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: Θ(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: Θ(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 106 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(⋅) 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é.
Opération
Tableau
Liste simplement chaînée
Lire ou écrire le i-ème élément
Θ(1)
Θ(i), donc Θ(n) au pire
Chercher une valeur (données non triées)
Θ(n)
Θ(n)
Chercher une valeur (données triées)
Θ(logn) par dichotomie
Θ(n): la dichotomie est impossible
Insérer en tête
Θ(n)
Θ(1)
Insérer en fin
Θ(1) amorti
Θ(1) avec un pointeur de queue, Θ(n) sinon
Insérer après une position connue
Θ(n)
Θ(1)
Supprimer une cellule de position connue
Θ(n)
Θ(1) si doublement chaînée
Mémoire par élément
la valeur seule
la valeur plus une ou deux adresses
Parcours complet
Θ(n), accès contigus
Θ(n), accès dispersés
Question 4.1
Un programme maintient un journal d'événements: il ajoute un événement à la fin des milliers de fois par seconde, et relit tout le journal du début à la fin une fois par heure. Il ne fait jamais d'accès par indice. Quelle structure choisir?
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 Θ(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 Θ(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.
Figure 4.1. La même séquence de huit opérations appliquée à une pile et à une file. Les deux structures reçoivent exactement les mêmes valeurs dans le même ordre; la pile rend 5, 9, 7, 3 et la file rend 3, 7, 5, 9. La case bordée de couleur est celle qui vient d'être ajoutée. Les deux colonnes de sortie sont produites par l'exécution de la séquence, pas recopiées.
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 106 éléments descend à une profondeur ⌈log2106⌉=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=106, en revanche, empile un million de blocs et provoque le débordement de pile (stack overflow) 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.
Question 4.2
On applique à une pile la séquence: empiler 1, empiler 2, empiler 3, dépiler, empiler 4, dépiler, dépiler, dépiler. Rangez les quatre valeurs dépilées dans l'ordre où elles sortent.
Glissez les éléments pour les mettre dans le bon ordre
1.
4
2.
3
3.
1
4.
2
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 2d. C'est vrai pour d=0: il y a une seule racine. Si les nœuds de profondeur d sont au plus 2d 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 2d+1. En sommant sur d=0,…,h,
n≤d=0∑h2d=2h+1−1.
Donc 2h+1≥n+1, soit h+1≥log2(n+1); comme h+1 est entier, h+1≥⌈log2(n+1)⌉. □
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 ⌈log2(n+1)⌉ tests. Pour n=7, elle donne h≥2; pour n=106, h≥19, donc au moins 20 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é.
Question 4.3
Un arbre binaire de recherche parfaitement équilibré contient n=1000000 de clés. Combien de comparaisons une recherche fait-elle au maximum? (Utilisez la borne du théorème 4.1, atteinte par un arbre équilibré: le nombre de comparaisons vaut h+1.)
La table de hachage
L'idée
La dichotomie et l'arbre équilibré descendent à log2n 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)=kmodm 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 ∣U∣>m — et c'est toujours le cas, puisque 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.
Figure 4.2. Une table de hachage à sept seaux avec chaînage séparé. Les six clés 12, 44, 13, 88, 23, 31 sont insérées dans cet ordre, la fonction h(k) = k mod 7 décide du seau, et la seule collision — 44 et 23 tombent toutes deux dans le seau 2 — est résolue en chaînant 23 derrière 44. Deux seaux restent vides bien que la table soit chargée à 86 pour cent: les collisions arrivent bien avant que la table ne soit pleine.
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
77⋅76⋅75⋅74⋅73⋅72=1176495040≈0,0428,
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 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 α éléments lorsque la clé est absente, et le résultat classique donne 1+α/2 comparaisons en moyenne lorsqu'elle est présente. Dans la table de la figure 4.2, α=6/7≈0,857, donc environ 0,86 comparaison pour un échec et 1,43 pour un succès.
Le point décisif est que α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 α dépasse un seuil, typiquement 0,75 — alors α reste borné par une constante, et les trois opérations (recherche, insertion, suppression) coûtent O(1) en moyenne. Le re-hachage coûte Θ(n) mais, par le même argument de doublement que pour les tableaux, il s'amortit en O(1) 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 Θ(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.
Question 4.4
Une table de hachage à chaînage possède m=500 seaux et contient n=400 clés. Sous l'hypothèse du hachage uniforme, combien de cellules une recherche infructueuse examine-t-elle en moyenne?
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 ∑vdeg(v). En groupant par arête, chaque arête {u,v} fournit exactement deux couples, (u,e) et (v,e): on obtient 2m. Les deux comptes sont égaux. Comme 2m 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 3,2,3,3,3,3,3,2 pour A,…,H: leur somme fait 22=2×11, conformément au théorème 4.2. Il est connexe, et il contient des cycles (par exemple A,B,E,C,A).
Deux représentations, deux factures
La matrice occupe n2 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:
Opération
Matrice d'adjacence
Listes d'adjacence
Mémoire
Θ(n2)
Θ(n+m)
Tester si u et v sont voisins
Θ(1)
Θ(degu)
Énumérer les voisins de u
Θ(n)
Θ(degu)
Ajouter ou retirer une arête
Θ(1)
Θ(degu)
Parcourir tout le graphe
Θ(n2)
Θ(n+m)
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 Θ(n2) avec une matrice contre Θ(n+m) avec des listes. Sur le réseau routier de l'exemple 4.3, c'est 108 contre 25000 opérations — un facteur 4000 obtenu sans toucher à une ligne de l'algorithme.
Question 4.5
Un graphe non orienté a n=10000 sommets et m=20000 arêtes. On doit répéter très souvent l'opération «énumérer les voisins d'un sommet». Quelle représentation choisir?
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:
Étape
Sommet visité
File après la visite
Distance depuis A
1
A
B, C, D
0
2
B
C, D, E
1
3
C
D, E, F
1
4
D
E, F, H
1
5
E
F, H, G
2
6
F
H, G
2
7
H
G
2
8
G
—
3
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):
Étape
Sommet visité
Pile après la visite
1
A
B, C, D
2
B
E, C, D
3
E
G, C, D
4
G
F, H, C, D
5
F
H, C, D
6
H
C, D
7
C
D
8
D
—
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 E, qui passe devant C et D; E dépose G, qui passe devant à son tour. En quatre étapes le parcours est descendu au fond du graphe, en G, le sommet le plus éloigné de A — alors que C et D, voisins immédiats de A, 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.
Figure 4.3. Le même graphe numéroté deux fois: en haut dans l'ordre du parcours en largeur depuis A, en bas dans l'ordre du parcours en profondeur depuis A. Les deux ordres sont calculés par le schéma du chapitre, le plus petit voisin traité en premier et un sommet marqué dès sa découverte. Le parcours en largeur épuise une couche avant de passer à la suivante; le parcours en profondeur plonge jusqu'au fond, atteint G en quatrième et laisse les voisins immédiats C et D pour la fin. Les rangs sont placés autour de chaque sommet par une règle de positions candidates qui écarte celles qui heurtent une arête, un sommet ou une autre étiquette.
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: Θ(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 Θ(m) pour l'exploration des listes. Au total Θ(n+m) avec des listes d'adjacence — et Θ(n2) avec une matrice, puisque énumérer les voisins d'un sommet y coûte n. Sur notre graphe, chacune des deux exécutions a fait 8=n extractions et 22=2m examens de voisins.
Explorateur 4.1 · Parcours d'un graphe, pas à pas
Le même graphe, le même code: seul le conteneur change. Une file donne le parcours en largeur, une pile le parcours en profondeur. Un sommet est marqué dès qu'il est découvert, et le plus petit voisin est toujours traité en premier.
Sommet de départA
Mode de parcourslargeur (file)
Étape4 / 8
Sommet courant
D
En attente
E F H
Sommets visités
4 / 8
Pourquoi le parcours en largeur donne les plus courts chemins
Notons δ(s,v) la distance de s à v: le nombre minimal d'arêtes d'un chemin de s à v, et +∞ 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 w depuis v, calcule exactement ces distances.
Démonstration. Établissons d'abord deux propriétés.
(i) d[v]≥δ(s,v) pour tout v découvert. Par récurrence sur l'ordre de découverte. On a d[s]=0=δ(s,s). Si w est découvert depuis v, alors d[w]=d[v]+1≥δ(s,v)+1 par hypothèse de récurrence; or l'arête {v,w} prolonge un chemin de longueur δ(s,v) en un chemin de longueur δ(s,v)+1 menant à w, donc δ(s,w)≤δ(s,v)+1≤d[w].
(ii) La file est monotone. À tout instant, si la file contient x1,…,xr de la tête vers la queue, alors d[x1]≤d[x2]≤⋯≤d[xr]≤d[x1]+1. C'est vrai au départ (la file ne contient que s). Un défilement retire x1 et ne peut que resserrer les inégalités. Un enfilement ajoute un w avec d[w]=d[x1]+1, où x1 est le sommet en cours de traitement, c'est-à-dire celui qui vient d'être défilé: la file avant l'ajout vérifie d[x1]≤d[xj]≤d[x1]+1, donc ajouter d[x1]+1 en queue conserve la croissance, et l'écart entre la tête et la queue reste au plus 1. Conséquence: les sommets sortent de la file par valeurs de d non décroissantes.
(iii) d[v]≤δ(s,v). Par récurrence sur k=δ(s,v). Pour k=0, v=s et d[s]=0. Supposons la propriété acquise pour tous les sommets à distance k, et soit v à distance k+1. Il existe un sommet u avec δ(s,u)=k et {u,v}∈E. Par hypothèse de récurrence d[u]=k, et u est défilé à un certain moment. Deux cas. Ou bien v n'est pas encore découvert quand u est traité: il l'est alors depuis u, et d[v]=d[u]+1=k+1. Ou bien v a été découvert plus tôt, depuis un sommet u′ défilé avant u; par (ii), d[u′]≤d[u]=k, donc d[v]=d[u′]+1≤k+1.
En combinant (i) et (iii), d[v]=δ(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. □
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 δ(A,F)=2 (le chemin A,C,F). Le sommet H est logé à la même enseigne. Le parcours en profondeur n'est donc pas 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 provisoired[v] — le poids du meilleur chemin connu jusqu'ici, initialisé à +∞ 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.
AB=4,BC=1,BE=10,DE=2,EF=3.AC=2,BD=5,CD=8,DF=6,
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 daprès les relâchements de cette étape.
Étape
Sommet rendu définitif
d[A]
d[B]
d[C]
d[D]
d[E]
d[F]
Initial
—
0
∞
∞
∞
∞
∞
1
A (0)
0
4
2
∞
∞
∞
2
C (2)
0
3
2
10
∞
∞
3
B (3)
0
3
2
8
13
∞
4
D (8)
0
3
2
8
10
14
5
E (10)
0
3
2
8
10
13
6
F (13)
0
3
2
8
10
13
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→C→D, soit 2+8), puis 8 (par A→C→B→D, soit 2+1+5). Et d[F] vaut 14 (par D) avant de tomber à 13 (par E). Une distance provisoire n'est pas une distance: elle est le meilleur chemin connu à cet instant, 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, d[F]=13, et le chemin optimal vers F est A→C→B→D→E→F, dont on vérifie le poids: 2+1+5+2+3=13. Remarquez qu'il emprunte cinq arêtes alors que F est à trois arêtes de A par A→B→D→F, dont le poids est 4+5+6=15. 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: Θ(n2) pour les extractions, Θ(m) pour les relâchements, soit Θ(n2) au total, puisque m≤n2. C'est le bon choix pour un graphe dense.
Avec une file de priorité implémentée par un tas binaire (binary heap) — une structure qui rend le minimum et l'insère en O(logn) —, on obtient O((n+m)logn). C'est le bon choix pour un graphe creux: sur le réseau routier de l'exemple 4.3, Θ(n2)=108 contre (n+m)log2n≈25000×13,3≈3,3⋅105.
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
Question 4.6
Sur le réseau fictif ci-dessus (AB=4, AC=2, BC=1, BD=5, BE=10, CD=8, DE=2, DF=6, EF=3), rangez les sommets dans l'ordre où l'algorithme de Dijkstra lancé depuis A les rend définitifs.
Glissez les éléments pour les mettre dans le bon ordre
1.
B
2.
E
3.
C
4.
D
5.
A
6.
F
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=109 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=1011, et la densité vaut 2m/(n(n−1))≈2⋅10−7.
La matrice d'adjacence est impossible. Elle compte n2=1018 cases. Même comprimée à un bit par case, elle occuperait 1018/8=1,25⋅1017 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 à 99,99998%.
Les listes d'adjacence tiennent. Il faut 2m=2⋅1011 références de 8 octets, plus 109 têtes de 8 octets, soit 1,608⋅1012 octets, environ 1,6 téraoctet: quelques disques. Le rapport entre les deux représentations est de 77736.
Le parcours suit. Un parcours en largeur complet coûte Θ(n+m)≈1,01⋅1011 opérations. À l'hypothèse de travail de 108 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 Θ(n2)=1018 opérations, soit 1010 secondes: 317 ans. 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
1+k+k(k−1)+k(k−1)2+⋯+k(k−1)d−1.(4.3)
Avec k=200, cette borne vaut 2,01⋅102 pour d=1, 4,00⋅104 pour d=2, 7,96⋅106 pour d=3 et 1,58⋅109 pour d=4: elle dépasse le milliard de comptes dès d=4.
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 Θ(1) et paie l'insertion en Θ(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 Θ(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.
L'arbre binaire de recherche coûte O(h) et non O(logn): sa hauteur dépend de l'ordre d'insertion, et des clés insérées triées le dégénèrent en liste chaînée. Le O(logn) est la propriété des arbres équilibrés (AVL, rouge-noir, arbres B). La table de hachage vise plus bas encore, O(1) en moyenne, mais ce O(1) est conditionné par la qualité de la fonction de hachage et par un facteur de charge borné, et son pire cas reste Θ(n): c'est une garantie échangée contre une moyenne.
Un graphe se représente par une matrice d'adjacence, Θ(n2) de mémoire, ou par des listes d'adjacence, Θ(n+m). Le seuil se calcule: en dessous d'environ 12% de densité les listes gagnent, et les graphes réels sont très en dessous — 0,32 Mo contre 12,5 Mo pour un réseau routier de 10000 carrefours, 1,6 To contre Po pour un graphe social de comptes.
Un seul schéma de parcours donne les deux algorithmes fondamentaux, selon que son conteneur est une file (largeur) ou une pile (profondeur); tous deux coûtent Θ(n+m). Le parcours en largeur calcule les plus courts chemins d'un graphe non pondéré, et c'est la monotonie de la file qui le démontre. Quand les arêtes sont pondérées, Dijkstra prend le relais en Θ(n2) ou O((n+m)logn) selon la structure choisie pour extraire le minimum — à la condition, utilisée explicitement dans sa preuve, que les poids soient positifs ou nuls.
Série d'exercices du chapitre 4Exercice 1 sur 5
Question 4.7
Un programme insère 105 éléments en tête d'une suite, puis la parcourt une seule fois du début à la fin. Quelle structure minimise le nombre total d'opérations élémentaires?
Exercices
Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.
Exercice 4.1 · Choisir une structure et compter
Pour chacun des trois usages suivants, dites quelle structure vous choisissez parmi tableau dynamique, liste doublement chaînée, arbre binaire de recherche équilibré et table de hachage, et justifiez par un compte d'opérations, pas par une impression.
Un annuaire de 106 collaborateurs interrogé 107 fois par jour par numéro d'identification exact, sans jamais d'ajout ni de suppression en cours de journée.
Une liste de lecture musicale dans laquelle l'utilisateur insère et retire des morceaux à des positions arbitraires qu'il vient de sélectionner à l'écran, et qu'il parcourt ensuite de proche en proche.
Un journal de températures horodatées dans lequel on veut, à tout moment, obtenir toutes les mesures d'un intervalle de temps donné.
Solution
1. Table de hachage. Le motif d'accès est exclusivement «cette clé exacte est-elle là, et que vaut-elle». Avec un facteur de charge maintenu sous 0,75, chaque requête coûte le calcul de h(k) et environ 1,4 comparaison en moyenne, soit de l'ordre de 107 opérations pour la journée. Un ABR équilibré coûterait ⌈log2(106+1)⌉=20 comparaisons par requête, soit 2⋅108 opérations: vingt fois plus. Un tableau trié avec dichotomie donne la même chose que l'ABR. Un tableau non trié donnerait 107×5⋅105=5⋅1012 comparaisons, soit, à 108 comparaisons par seconde, près de quatorze heures. L'absence d'ajouts pendant la journée est ce qui rend le hachage sans risque ici: le facteur de charge ne peut pas dériver.
2. Liste doublement chaînée. L'énoncé dit que la position est déjà sélectionnée, donc déjà tenue: l'insertion et la suppression coûtent alors Θ(1) chacune, quelle que soit la longueur de la liste. Un tableau dynamique coûterait Θ(n) par opération, car il faut décaler la queue. Le parcours «de proche en proche» est Θ(n) dans les deux cas, et le double chaînage permet de reculer aussi bien que d'avancer. L'ABR et la table de hachage sont hors sujet: ils ne représentent pas un ordre choisi par l'utilisateur, seulement un ordre de clés ou aucun ordre.
3. Arbre binaire de recherche équilibré, clé = horodatage. C'est le seul des quatre candidats qui réponde aux requêtes par intervalle: on descend jusqu'à la borne inférieure en O(logn), puis on continue le parcours infixe tant qu'on ne dépasse pas la borne supérieure, pour un coût total de O(logn+r) où r est le nombre de mesures rendues — ce qui est optimal, puisqu'il faut bien les énumérer. La table de hachage est ici disqualifiée par construction: elle disperse volontairement les clés voisines, et répondre à un intervalle lui demanderait de balayer toute la table. Un tableau trié par horodatage convient aussi tant que les mesures arrivent dans l'ordre chronologique — ce qui est le cas d'un journal — et il est même préférable, car l'ajout se fait toujours en fin en Θ(1) amorti et la dichotomie donne la borne inférieure en Θ(logn) avec de meilleurs facteurs constants. ; celle qui ne l'est pas est la table de hachage.
Exercice 4.2 · Une pile qui évalue une expression
La notation postfixée (ou polonaise inverse) écrit les opérandes avant l'opérateur: 3 4 + vaut 7. Elle s'évalue avec une pile: on lit les symboles de gauche à droite; un nombre est empilé; un opérateur dépile ses deux opérandes, calcule, et empile le résultat.
Évaluez 3 4 + 2 * 7 - en donnant l'état de la pile après chaque symbole.
Pourquoi faut-il faire attention à l'ordre des deux dépilements pour une soustraction ou une division?
Que se passe-t-il si l'expression est mal formée, par exemple 3 4 + +? Quel test simple permet de le détecter?
Quelle est la hauteur maximale atteinte par la pile lors de l'évaluation de 3 4 + 2 * 7 -, et que mesure cette hauteur?
Solution
1. Voici la trace, produite par l'exécution:
Symbole
Action
Pile après (fond → sommet)
3
empiler 3
3
4
empiler 4
3, 4
+
dépiler 4 et 3, empiler 3+4=7
7
2
empiler 2
7, 2
*
dépiler 2 et 7, empiler 7×2=14
14
7
empiler 7
14, 7
-
dépiler 7 et 14, empiler 14−7=7
7
Le résultat est 7, ce qui correspond bien à (3+4)×2−7.
2. Le premier dépilement rend l'opérande de droite, le second celui de gauche, puisque la pile est LIFO et que l'opérande de droite a été empilé en dernier. Pour une soustraction il faut donc calculer second - premier et non l'inverse: sur 14 7 -, on dépile 7 puis 14 et on doit rendre 14−7=7, pas 7−14=−7. L'addition et la multiplication, commutatives, pardonnent l'erreur; la soustraction et la division ne la pardonnent pas, et c'est un bogue classique.
3. Sur 3 4 + +, les trois premiers symboles laissent la pile réduite à {7}; le second + veut dépiler deux opérandes et n'en trouve qu'un: la pile se vide avant la fin. Le test est double et suffit: (a) à chaque opérateur binaire, la pile doit contenir au moins deux éléments; (b) à la fin de la lecture, la pile doit contenir exactement un élément. Une expression comme 3 4 5 + passe le test (a) mais échoue au test (b), la pile finissant à deux éléments.
4. La pile atteint la hauteur 2 (après 3 4, après 7 2 et après 14 7). Cette hauteur maximale mesure le nombre de résultats intermédiaires qu'il faut retenir simultanément, c'est-à-dire la profondeur d'imbrication de l'expression. C'est exactement la quantité qu'un compilateur cherche à minimiser lorsqu'il alloue les registres d'un processeur: une expression de hauteur de pile h demande h registres pour être évaluée sans écrire en mémoire.
Exercice 4.3 · Arbres binaires de recherche et ordre d'insertion
Insérez les clés 50,30,70,20,40,60,80 dans cet ordre dans un ABR vide. Dessinez l'arbre, donnez sa hauteur, et le nombre de comparaisons qu'il a fallu pour les sept insertions.
Faites de même avec le même ensemble de clés inséré dans l'ordre 20,30,40,50,60,70,80, puis dans l'ordre 20,80,30,70,40,60,50.
Dans chacun des trois arbres, combien de comparaisons coûte la recherche de la clé 80? Et celle de la clé 45, absente?
Donnez le parcours infixe de chacun des trois arbres. Que constatez-vous, et pourquoi?
Solution
1. L'insertion donne un arbre parfaitement équilibré:
50
/ \
30 70
/ \ / \
20 40 60 80
Sa hauteur est 2, ce qui est le minimum autorisé par le théorème 4.1 pour n=7 (⌈log28⌉−1=2). Les insertions ont coûté 0+1+1+2+2+2+2=10 comparaisons.
Exercice 4.4 · Un graphe, deux représentations, deux parcours
Soit le graphe non orienté G à six sommets 1,…,6 et d'arêtes {1,2},{1,3},{2,4},{3,4},{3,5},{4,6},{5,6}.
Donnez sa matrice d'adjacence et ses listes d'adjacence. Vérifiez le lemme des poignées de main.
Donnez l'ordre de visite d'un parcours en largeur depuis le sommet 1, voisins pris par numéro croissant, ainsi que la distance de 1 à chaque sommet.
Donnez l'ordre de visite d'un parcours en profondeur depuis le sommet 1, avec le schéma du cours: même convention (le plus petit voisin sort du conteneur en premier) et marquage à la découverte. Donnez aussi le contenu de la pile après chaque visite.
G contient-il un cycle? Combien d'arêtes faudrait-il retirer au minimum pour qu'il n'en contienne plus, tout en restant connexe?
Ce graphe se stocke-t-il plus économiquement en matrice ou en listes? Et s'il avait 105 sommets et 2⋅105 arêtes?
Solution
1. Les degrés sont deg(1)=2, deg(2)=2, deg(3)=3, deg(4)=3, deg(5)=2, , de somme : le lemme des poignées de main est vérifié avec .
Exercice 4.5 · Autour de Dijkstra
Montrez que si toutes les arêtes ont le poids 1, l'algorithme de Dijkstra rend les mêmes distances que le parcours en largeur. Les deux algorithmes rendent-ils les sommets définitifs dans le même ordre?
Démontrez que, dans l'exécution de Dijkstra sur un graphe à poids positifs ou nuls, la suite des valeurs d[u] des sommets successivement rendus définitifs est croissante au sens large.
On propose la «correction» suivante pour traiter les poids négatifs: ajouter une même constante c à tous les poids pour les rendre positifs, appliquer Dijkstra, puis retrancher. Montrez sur un exemple que cette idée est fausse.
Sur le réseau fictif du cours (AB=4, AC=2, BC=1, BD=5, BE=10, CD=8, DE=2, DF=6, EF=3), que devient la distance de A à F si l'arête DE passe de 2 à 9?
Solution
1. Avec des poids tous égaux à 1, le poids d'un chemin est son nombre d'arêtes, donc δw=δ et les deux algorithmes calculent la même fonction. Plus précisément, on peut voir le parcours en largeur comme le cas particulier de Dijkstra où la file de priorité est remplacée par une file ordinaire: la monotonie (ii) de la preuve du théorème 4.3 dit que la file contient au plus deux valeurs consécutives de d et qu'elles y sont croissantes, de sorte que «prendre la tête de la file» est «prendre le minimum». L'ordre de mise au définitif est donc croissant en distance dans les deux cas, mais il peut différer à l'intérieur d'une couche: à égalité de distance, le parcours en largeur sert dans l'ordre de découverte, tandis que Dijkstra sert dans un ordre qui dépend de l'implémentation de sa file de priorité. Les distances sont identiques, l'ordre ne l'est pas nécessairement.
2. Soient u1,u2,…,un les sommets rendus définitifs dans cet ordre, et montrons où désigne la valeur au moment où est rendu définitif. Au moment où est choisi, est encore non définitif, donc par la règle de choix du minimum, . Ensuite, ne peut changer que par un relâchement depuis , qui lui donne la valeur puisque le poids est positif ou nul. Dans les deux cas — valeur inchangée ou valeur réécrite — on a , et la suite est croissante au sens large. : un relâchement peut alors faire descendre en dessous de , ce qui est exactement la façon dont l'algorithme se trompe.
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».
49500
27
82
7
8
10000
8
30000×8+10000×8=320000
0,32 Mo
Rapport: la matrice la plus compacte coûte encore 39 fois plus que les listes; la matrice d'octets, 312 fois plus. La quasi-totalité des 108 cases contiennent un zéro.
6,41 Mo
Rapport inversé: les listes coûtent ici 51 fois la matrice de bits et 6,4 fois la matrice d'octets.
m<62000
12,4%
n=10000
m<6245000
12,5%
en dessous d'une dizaine de pour cent de densité, les listes; au-dessus, la matrice
d[C]=2
B
1
B
A→C→B
2−2=0
C
B
1
0
125
109
Problème guidé 4.1 · Le réseau de navettes d'un campus fictif
Un campus fictif compte six arrêts de navette, P, Q, R, S, T et U. Les liaisons directes et leurs durées en minutes sont: PQ=3, PR=7, QR=2, QS=7, RT=3, ST=1, SU=5, TU=8. Toutes les liaisons se parcourent dans les deux sens. Ces valeurs sont inventées pour l'exercice. On veut choisir une représentation, compter les liaisons, puis comparer le trajet ayant le moins de correspondances au trajet le plus rapide entre P et U.
1
Le graphe et son bilan de degrés
Le graphe a n=6 sommets. Comptez ses arêtes et vérifiez le lemme des poignées de main: les degrés valent deg(P)=2, deg(Q)=3, deg(R)=3, deg(S)=3, deg(T)=3, deg(U)=2.
Question
Combien le graphe a-t-il d'arêtes?
Le trajet avec le moins de correspondances
Le trajet le plus rapide
La morale
Les deux réponses sont acceptables si elles sont argumentées
2. Avec les clés triées, chaque nouvelle clé part systématiquement à droite: l'arbre est une chaîne descendante 20→30→40→50→60→70→80, de hauteur 6, obtenue au prix de 0+1+2+3+4+5+6=21 comparaisons.
Avec l'ordre 20,80,30,70,40,60,50, on obtient une chaîne «en zigzag»: 20 est la racine, 80 son fils droit, 30 le fils gauche de 80, 70 le fils droit de 30, 40 le fils gauche de 70, 60 le fils droit de 40, 50 le fils gauche de 60. La hauteur est encore 6 et le coût des insertions encore 21 comparaisons. La dégénérescence n'exige donc pas des données triées: il suffit que chaque clé nouvelle tombe toujours du même côté du dernier nœud atteint.
3. Dans l'arbre équilibré, chercher 80 coûte 3 comparaisons (50, 70, 80) et chercher 45 en coûte 3 (50, 30, 40, puis un fils droit vide). Dans la chaîne croissante, chercher 80 coûte 7 comparaisons — toute la chaîne — et chercher 45 en coûte 4 (20, 30, 40, 50, puis un fils gauche vide). Dans la chaîne en zigzag, chercher 80 ne coûte que 2 comparaisons, puisque 80 y est juste sous la racine, mais chercher 45 en coûte 7: il faut descendre jusqu'à la feuille 50. Le pire cas d'un arbre dégénéré est h+1=7 comparaisons, atteint pour une clé différente selon la forme de l'arbre.
4. Le parcours infixe des trois arbres donne la même suite: 20,30,40,50,60,70,80. C'est une conséquence directe de la propriété d'ordre. Démontrons-la par récurrence sur la taille: pour un arbre vide c'est trivial; pour un arbre de racine x, le parcours infixe concatène le parcours du sous-arbre gauche, la clé de x, et le parcours du sous-arbre droit. Par hypothèse de récurrence les deux parcours sont croissants, et la propriété d'ordre garantit que toutes les clés de gauche sont < à celle de x et toutes celles de droite >: la concaténation est donc croissante. Un ABR est ainsi une structure «triée en permanence», quelle que soit sa forme — seul son coût d'accès dépend de sa forme.
deg(6)=2
14=2×7
m=7
Matrice d'adjacence (lignes et colonnes dans l'ordre 1 à 6):
1
2
3
4
5
6
1
0
1
1
0
0
0
2
1
0
0
1
0
0
3
1
0
0
1
1
0
4
0
1
1
0
0
1
5
0
0
1
0
0
1
6
0
0
0
1
1
0
Elle est symétrique, sa diagonale est nulle (pas de boucle), et elle contient 14 uns, soit 2m. Listes d'adjacence: 1→2,3; 2→1,4; 3→1,4,5; 4→2,3,6; 5→3,6; 6→4,5.
2. On visite 1 (file: 2,3), puis 2 (file: 3,4), puis 3 (file: 4,5), puis 4 (file: 5,6), puis 5 (file: 6), puis 6. L'ordre est 1,2,3,4,5,6 et les distances sont δ(1,1)=0, δ(1,2)=δ(1,3)=1, δ(1,4)=δ(1,5)=2, δ(1,6)=3.
3. On empile les voisins en ordre décroissant pour que le plus petit soit dépilé en premier, et l'on marque chaque sommet dès qu'on l'empile. Le sommet 1 empile 3 puis 2; on dépile 2, qui empile 4; on dépile 4, qui empile 6 (3 est déjà marqué); on dépile 6, qui empile 5; on dépile 5 (ses voisins 3 et 6 sont marqués), puis enfin 3, resté au fond depuis la première étape. La trace est:
Étape
Sommet visité
Pile après la visite (sommet à gauche)
1
1
2, 3
2
2
4, 3
3
4
6, 3
4
6
5, 3
5
5
3
6
3
—
L'ordre est 1,2,4,6,5,3. Remarquez que 5 est découvert depuis 6, donc par le chemin 1,2,4,6,5 de longueur 4, alors que δ(1,5)=2 par 1,3,5: le parcours en profondeur ne mesure aucune distance. Remarquez aussi que 3, voisin immédiat de 1, est visité en dernier — il a été marqué à la première étape et a attendu au fond de la pile pendant tout le parcours.
4. Oui: 1,2,4,3,1 en est un, et 3,4,6,5,3 aussi. Un graphe connexe à n sommets sans cycle est un arbre et possède exactement n−1 arêtes; ici n−1=5 alors que m=7. Il faut donc retirer au moins deux arêtes, et deux suffisent si on les choisit bien: retirer {2,4} et {5,6} laisse les arêtes {1,2},{1,3},{3,4},{3,5},{4,6}, soit cinq arêtes formant un arbre couvrant connexe. En revanche, retirer {1,2} et {2,4} déconnecterait le sommet 2.
5. Pour n=6: la matrice compte 36 cases, soit 36 octets à un octet par case; les listes comptent 2m+n=14+6=20 références de 8 octets, soit 160 octets. La matrice gagne, et c'est normal: la densité vaut 14/30≈0,47, très au-dessus du seuil de 12% de l'exemple 4.3. Pour n=105 et m=2⋅105: la matrice compte 1010 cases, soit 10 Go à un octet par case ou 1,25 Go à un bit; les listes coûtent (4⋅105+105)×8=4⋅106 octets, soit 4 Mo. Les listes gagnent d'un facteur 312 face à la matrice de bits, et 2500 face à la matrice d'octets. La densité y vaut 4⋅10−5.
d[ui]≤d[ui+1]
d[u]
u
ui
ui+1
d[ui]≤dalors[ui+1]
d[ui+1]
ui
d[ui]+w(ui,ui+1)≥d[ui]
d[ui+1]≥d[ui]
C'est faux avec un poids négatif
d[ui+1]
d[ui]
3. L'idée est fausse parce que le décalage ajouté à un chemin vaut cpar arête, et dépend donc du nombre d'arêtes du chemin, qui n'est pas le même pour tous les chemins. Exemple: arcs A→B de poids 1, A→C de poids 2, C→B de poids −2, et c=2. Les poids décalés sont 3, 4 et 0. Dijkstra sur le graphe décalé donne d′[B]=min(3,4+0)=3, atteint par l'arc direct. Mais dans le graphe d'origine, A→B pèse 1 et A→C→B pèse 2−2=0: l'optimum est le chemin à deux arcs. Le décalage l'a pénalisé de 2c=4 alors qu'il n'a pénalisé le chemin à un arc que de c=2. Le décalage ne préserve pas l'ordre des chemins, donc il ne préserve pas l'optimum.
4. Reprenons l'exécution avec DE=9. A définitif: d[B]=4, d[C]=2. C définitif (2): d[B]→3, d[D]→10. B définitif (3): d[D]→8, d[E]→13. D définitif (8): d[E] resterait 8+9=17, ce qui n'améliore pas 13, donc d[E] reste 13; d[F]→8+6=14. F définitif (14) avant E (13)? Non: 13<14, donc E est rendu définitif (13) et relâche F à 13+3=16, ce qui n'améliore pas 14. F est enfin définitif à 14, par le chemin A→C→B→D→F de poids 2+1+5+6=14. La distance est passée de 13 à 14 et le chemin optimal a changé: il passe désormais directement de D à F au lieu de faire le détour par E, qui est devenu trop cher. Notez que l'ordre des sommets définitifs a lui aussi changé, E passant après D mais avant F.