Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › La file : parcours en largeur et fenêtre monotone

La file : parcours en largeur et fenêtre monotone

Piles, files et tasavance

La file sert à explorer par vagues. Son application principale est le parcours en largeur.

Deque<Integer> file = new ArrayDeque<>();
file.offer(x);       // ajouter en queue
file.poll();         // retirer en tête, null si vide
file.peek();         // consulter la tête

Le BFS, avec le motif « par niveau » :

static int nombreEtapes(Noeud depart, Noeud cible) {
    Deque<Noeud> file = new ArrayDeque<>();
    Set<Noeud> visites = new HashSet<>();
    file.offer(depart);
    visites.add(depart);                       // marquer à l'AJOUT
    int niveau = 0;

    while (!file.isEmpty()) {
        int tailleNiveau = file.size();        // ← le nombre de nœuds de ce niveau
        for (int i = 0; i < tailleNiveau; i++) {
            Noeud n = file.poll();
            if (n.equals(cible)) return niveau;
            for (Noeud voisin : n.voisins())
                if (visites.add(voisin)) file.offer(voisin);   // add renvoie false si déjà vu
        }
        niveau++;
    }
    return -1;
}

Deux détails font toute la différence : marquer à l'ajout (sinon un nœud entre plusieurs fois dans la file) et mémoriser file.size() (sinon impossible de compter les niveaux).

Sur un graphe non pondéré, le BFS donne le plus court chemin : les nœuds à distance d sont tous traités avant ceux à distance d+1.

Les termes à connaître

File (FIFO)

Premier entré, premier sorti. En Java : Deque/ArrayDeque avec offer (ajouter en queue) et poll (retirer en tête), tous deux en O(1).

Parcours en largeur (BFS)

Explorer niveau par niveau à partir d'une source, à l'aide d'une file. Sur un graphe non pondéré, il donne le plus court chemin.

Traitement par niveau

Mémoriser file.size() au début de chaque tour pour traiter exactement un niveau : c'est ce qui permet de compter les étapes ou de grouper par profondeur.

Ensemble des visités

Marquer un nœud au moment où on l'ajoute à la file, pas quand on le retire. Sinon le même nœud peut être empilé plusieurs fois.

File monotone

Un Deque dont les valeurs restent décroissantes, utilisé pour connaître le maximum de chaque fenêtre glissante en O(n).

poll vs remove

poll() renvoie null sur une file vide, remove() lève une exception. Même distinction entre offer/add et peek/element.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.