Ranger pour mieux chercher : piles, files, dictionnaires, arbres et graphes

Ctrl+Z annule ta dernière action, puis l'avant-dernière : c'est une pile. Ton imprimante traite les documents dans leur ordre d'arrivée : une file. Ton répertoire retrouve un numéro à partir d'un nom : un dictionnaire. Un tableau de tournoi est un arbre, la carte du métro un graphe. Bien choisir sa structure rend un programme simple et rapide.

1. Interface et implémentation

Une structure de données se définit par son interface, les opérations qu'elle offre, et son implémentation, la façon de les programmer : on peut changer la seconde sans toucher aux programmes qui utilisent la première.

2. Piles et files

Une pile (LIFO, last in, first out) : on empile au sommet et on dépile le dernier arrivé. Une file (FIFO, first in, first out) : on enfile en queue et on défile le premier arrivé.

from collections import deque

pile = []
for page in ["accueil", "profil", "photos"]:
 pile.append(page) # empiler
print(pile.pop()) # photos : dernier entré, premier sorti

file = deque()
for client in ["Ana", "Bilal", "Chloé"]:
 file.append(client) # enfiler
print(file.popleft()) # Ana : premier entré, premier sorti

Une liste Python fait une excellente pile. Pour une file, préfère deque : liste.pop(0) décale tous les éléments suivants, lent sur une longue file.

3. Dictionnaires

Un dictionnaire associe des clés, toutes différentes, à des valeurs. Grâce à une table de hachage, l'accès par la clé prend en moyenne un temps constant, même pour un énorme dictionnaire.

mots = "le chat voit le chien et le chat fuit".split()
compte = {}
for m in mots:
 compte[m] = compte.get(m, 0) + 1
print(compte["le"], compte["chat"], len(compte)) # 3 2 6

compte.get(m, 0) renvoie la valeur de la clé m, ou 0 si elle est absente. Une clé doit être non modifiable : chaîne, nombre ou tuple, jamais une liste.

4. Arbres binaires

Un arbre binaire est vide, ou formé d'un nœud (la racine) relié à deux sous-arbres, gauche et droit. Un nœud sans enfant est une feuille. La taille est le nombre de nœuds ; la hauteur, le nombre de nœuds du plus long chemin de la racine à une feuille (ici, un nœud seul a pour hauteur 1 ; certains manuels comptent 0 : lis bien la convention de l'énoncé).

 8
 / \
 3 10
 / \ \
 1 6 14

class Noeud:
 def __init__(self, gauche, valeur, droite):
 self.gauche = gauche
 self.valeur = valeur
 self.droite = droite

def hauteur(a):
 if a is None: # arbre vide
 return 0
 return 1 + max(hauteur(a.gauche), hauteur(a.droite))

def infixe(a):
 if a is not None:
 infixe(a.gauche)
 print(a.valeur, end=" ")
 infixe(a.droite)

arbre = Noeud(Noeud(Noeud(None, 1, None), 3, Noeud(None, 6, None)),
 8, Noeud(None, 10, Noeud(None, 14, None)))
print(hauteur(arbre)) # 3
infixe(arbre) # 1 3 6 8 10 14

Trois parcours en profondeur, selon le moment où l'on traite la racine : préfixe (racine, gauche, droite) donne 8 3 1 6 10 14 ; infixe (gauche, racine, droite) donne 1 3 6 8 10 14 ; suffixe (gauche, droite, racine) donne 1 6 3 14 10 8.

Cet arbre est un arbre binaire de recherche (ABR) : pour chaque nœud, les clés à gauche sont plus petites et celles à droite plus grandes. Son parcours infixe sort les clés triées, et chercher 6 ne demande que trois comparaisons (8, puis 3, puis 6) : on descend une seule branche.

5. Graphes et parcours

Un graphe est formé de sommets reliés par des arêtes. On le représente souvent par un dictionnaire de listes d'adjacence : à chaque sommet, la liste de ses voisins.

from collections import deque

graphe = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
 "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def largeur(graphe, depart):
 vus = [depart]
 file = deque([depart])
 while file:
 s = file.popleft()
 for v in graphe[s]:
 if v not in vus:
 vus.append(v)
 file.append(v)
 return vus

def profondeur(graphe, s, vus):
 vus.append(s)
 for v in graphe[s]:
 if v not in vus:
 profondeur(graphe, v, vus)
 return vus

print(largeur(graphe, "A")) # ['A', 'B', 'C', 'D', 'E', 'F']
print(profondeur(graphe, "A", [])) # ['A', 'B', 'D', 'E', 'F', 'C']

Le parcours en largeur utilise une file : il visite les voisins de A, puis les voisins des voisins… Il trouve donc le plus court chemin en nombre d'arêtes. Le parcours en profondeur, récursif (donc avec une pile, celle des appels), va au bout d'un chemin avant de revenir en arrière, comme dans un labyrinthe.

À retenir

• Pile : dernier entré, premier sorti ; file : premier entré, premier sorti (deque en Python).
• Un dictionnaire donne accès à une valeur par sa clé, en temps constant en moyenne.
• Taille, hauteur et parcours d'un arbre binaire se programment récursivement ; le parcours infixe d'un ABR donne les clés triées.
• Un graphe se code par listes d'adjacence ; le parcours en largeur (file) trouve les plus courts chemins en nombre d'arêtes, le parcours en profondeur (récursif) explore une branche jusqu'au bout.

★ Pour aller plus loin

La théorie des graphes naît en 1736, quand Leonhard Euler prouve qu'on ne peut pas traverser une seule fois chacun des sept ponts de Königsberg. Aujourd'hui, ton GPS cherche des plus courts chemins dans un graphe pondéré avec des descendants de l'algorithme d'Edsger Dijkstra, publié en 1959.

Un ABR mal rempli (clés insérées déjà triées) devient un long fil, et la recherche redevient lente ; les arbres AVL (1962) se rééquilibrent tout seuls. Depuis Python 3.7, un dictionnaire garde aussi l'ordre d'insertion de ses clés.

Sources pour creuser

• Numérique et sciences informatiques, Terminale : 24 leçons avec exercices corrigés, Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre et Kim Nguyen (Ellipses).
• Algorithmes : notions de base, Thomas H. Cormen (Dunod).
• Sur interstices.info (Inria), cherche « graphe ».
• Sur lumni.fr, cherche « algorithme » ; le site visualgo.net (en anglais) anime piles, files, arbres et parcours de graphes.
• Des exercices progressifs sur france-ioi.org.