Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe du parcours en profondeur et du parcours en largeur ;

• implémenter un DFS récursif et un DFS itératif avec une pile ;

• implémenter un BFS avec une file ;

• utiliser un tableau de marquage pour éviter les répétitions et les boucles infinies ;

• construire une forêt de parcours et identifier les composantes connexes ;

• rechercher un chemin et reconstruire ce chemin à l’aide des prédécesseurs ;

• calculer des distances minimales dans un graphe non pondéré ;

• appliquer les parcours à la connexité, aux labyrinthes et à la détection de cycles ;

• analyser la complexité temporelle et spatiale des parcours.

Prérequis

• représentation des graphes par listes ou matrices d’adjacence ;

• piles, files et récursivité ;

• tableaux, listes et dictionnaires ;

• notions de chemin, cycle, degré et composante ;

• complexité en O(n + m).

Organisation indicative

Introduction générale

La représentation d’un graphe décrit quelles relations existent. Un parcours exploite cette représentation pour visiter méthodiquement les sommets et les arêtes. Les deux parcours fondamentaux sont le parcours en profondeur, souvent noté DFS, et le parcours en largeur, souvent noté BFS.

Ces parcours constituent la base de nombreux algorithmes : recherche d’un chemin, calcul de distances non pondérées, détection de connexité, construction de composantes, exploration de labyrinthes, détection de cycles et analyse de dépendances.

Figure 17.1 — Graphe non orienté utilisé comme exemple fil rouge.

17.1 Parcours en profondeur

17.1.1 Principe général

Le parcours en profondeur explore une branche aussi loin que possible avant de revenir au dernier sommet possédant encore un voisin non visité. Ce retour en arrière est naturellement géré par la pile d’appels récursifs ou par une pile explicite.

1. Marquer le sommet courant comme visité.

2. Traiter le sommet selon le besoin de l’application.

3. Choisir un voisin non visité et poursuivre l’exploration.

4. Revenir en arrière lorsque tous les voisins ont été examinés.

17.1.2 Marquage des sommets

Sans marquage, un algorithme pourrait revisiter indéfiniment les mêmes sommets lorsqu’un cycle existe. Un tableau Visite, indexé par sommet, mémorise les sommets déjà découverts.

17.1.3 Version récursive

Trace sur le graphe fil rouge

Depuis A et avec des voisins examinés par ordre alphabétique, un ordre possible est : A, B, C, E, D, F. La structure exacte dépend de l’ordre des voisins dans les listes d’adjacence.

17.1.4 Version itérative avec une pile

Une pile explicite évite la dépendance à la profondeur maximale de récursion. Deux variantes existent : marquer un sommet lors de son empilement ou lors de son dépilement. Le marquage à l’empilement évite les insertions multiples.

17.1.5 Détection des composantes

Dans un graphe non orienté, un DFS lancé depuis un sommet visite exactement sa composante connexe. Pour traiter tout le graphe, on relance un DFS depuis chaque sommet encore non visité. L’ensemble des arbres obtenus constitue une forêt DFS.

Figure 17.2 — Une forêt DFS contient un arbre par composante connexe.

17.1.6 Complexité du DFS

Avec des listes d’adjacence, chaque sommet est marqué une fois et chaque arête est examinée au plus deux fois dans un graphe non orienté. La profondeur de la pile peut atteindre n dans un graphe en forme de chaîne.

17.2 Parcours en largeur

17.2.1 Principe général

Le parcours en largeur visite les sommets par couches successives : d’abord la source, puis tous ses voisins, ensuite les sommets situés à distance deux, et ainsi de suite. La file garantit que les sommets sont traités dans l’ordre de leur découverte.

1. Enfiler la source et la marquer.

2. Défiler le sommet le plus ancien.

3. Découvrir tous ses voisins encore non visités.

4. Enfiler ces voisins et répéter jusqu’à ce que la file soit vide.

17.2.2 BFS avec une file

Figure 17.3 — Un BFS depuis A organise les sommets par distance minimale.

17.2.3 Trace de la file

17.2.4 Distance minimale en nombre d’arêtes

Dans un graphe non pondéré, le BFS calcule le nombre minimal d’arêtes entre la source et chaque sommet accessible. Cette propriété ne s’applique pas directement aux graphes pondérés, sauf lorsque tous les poids sont identiques.

17.2.5 Reconstruction d’un chemin

Le tableau Parent enregistre le sommet à partir duquel chaque sommet a été découvert. Pour reconstruire le chemin, on part de la cible et on remonte jusqu’à la source, puis on inverse la séquence.

17.2.6 BFS sur un graphe non connexe

Comme le DFS, un BFS lancé depuis une seule source reste limité à sa composante. Pour parcourir tout le graphe, on relance un BFS depuis chaque sommet non visité.

17.2.7 Complexité du BFS

17.2.8 Comparaison DFS / BFS

17.3 Applications

17.3.1 Recherche d’un chemin

Pour savoir si un chemin existe entre s et t, un DFS ou un BFS suffit. Si l’on veut un chemin comportant un nombre minimal d’arêtes, on utilise un BFS. Pour obtenir un chemin quelconque, les deux méthodes conviennent.

17.3.2 Détection de connexité

Un graphe non orienté est connexe si un parcours lancé depuis n’importe quel sommet visite les n sommets. Pour un graphe vide, la convention doit être précisée.

17.3.3 Exploration d’un labyrinthe

Une grille peut être vue comme un graphe implicite : chaque case libre est un sommet et deux cases voisines sont reliées lorsqu’un déplacement est autorisé. Le BFS trouve un chemin comportant un nombre minimal de déplacements ; le DFS trouve un chemin éventuel sans garantir qu’il soit court.

Figure 17.4 — Exemple de chemin dans une grille ; chaque case libre représente un sommet.

17.3.4 Détection simple d’un cycle

Cycle dans un graphe non orienté

Lors d’un DFS, rencontrer un voisin déjà visité ne prouve pas toujours un cycle : ce voisin peut être le parent du sommet courant. Un cycle existe lorsque l’on rencontre un voisin visité différent du parent.

Cycle dans un graphe orienté

Dans un graphe orienté, on utilise trois couleurs : blanc pour non visité, gris pour en cours d’exploration et noir pour terminé. Un arc vers un sommet gris révèle un cycle dirigé.

17.3.5 Calcul des composantes connexes

Une composante connexe est un ensemble maximal de sommets reliés entre eux par des chemins. Le nombre de lancements de DFS ou de BFS nécessaires pour visiter tout le graphe est égal au nombre de composantes.

Méthode de choix entre DFS et BFS

Erreurs fréquentes et bonnes pratiques

Bonnes pratiques de conception

• séparer la structure du graphe de l’algorithme de parcours ;

• rendre explicite l’ordre des voisins lorsque le résultat doit être reproductible ;

• conserver les parents lorsque l’application demande un chemin ;

• conserver les distances uniquement lorsqu’elles sont utiles ;

• prévoir le cas d’une source absente ou d’un graphe vide ;

• tester les graphes isolés, cycliques, en chaîne, en étoile et non connexes ;

• instrumenter le nombre de sommets et d’arêtes examinés pour valider l’analyse.

Travaux dirigés

Les exercices suivants supposent que les voisins sont examinés par ordre alphabétique, sauf indication contraire.

TD 1 — Tracer un DFS

• Donner l’ordre du DFS récursif du graphe fil rouge depuis A.

• Construire le tableau Parent.

• Dessiner l’arbre DFS obtenu.

TD 2 — Tracer un BFS

• Donner l’ordre du BFS depuis A.

• Compléter les distances et les parents.

• Reconstituer un chemin minimal de A vers F.

TD 3 — Ordres de voisinage

• Reprendre le DFS avec des voisins examinés dans l’ordre inverse.

• Comparer l’ordre de visite et l’ensemble des sommets atteints.

• Expliquer ce qui reste invariant.

TD 4 — Graphe non connexe

• Pour le graphe composé de {A,B,C,D}, {E,F} et {G}, déterminer le nombre de composantes.

• Donner une forêt de parcours possible.

TD 5 — Recherche de chemin

• Proposer un algorithme qui s’arrête dès que la cible est découverte.

• Préciser comment reconstruire le chemin.

TD 6 — Cycle non orienté

• Expliquer pourquoi l’arête vers le parent doit être ignorée.

• Appliquer l’algorithme à un triangle puis à une chaîne.

TD 7 — Cycle orienté

• Appliquer la méthode des trois couleurs à A→B, B→C, C→A.

• Appliquer-la à A→B, A→C, B→D, C→D.

TD 8 — Labyrinthe

• Modéliser une grille 4×4 contenant des obstacles.

• Indiquer les voisins d’une case intérieure et d’une case de bord.

• Choisir DFS ou BFS pour obtenir un trajet minimal.

TD 9 — Analyse de complexité

• Justifier O(n+m) pour un BFS sur listes d’adjacence.

• Expliquer pourquoi une matrice conduit à O(n²).

TD 10 — Choix de méthode

• Choisir DFS ou BFS pour : distance sociale, détection d’un cycle dirigé, composantes et recherche d’un chemin quelconque.

• Justifier chaque choix.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

Un ordre possible est A, B, C, E, D, F. Les parents possibles sont Parent[B]=A, Parent[C]=B, Parent[E]=C, Parent[D]=E et Parent[F]=D. Un autre ordre reste valide si l’ordre des voisins diffère.

Correction du TD 2

L’ordre BFS est A, B, C, D, E, F. Les distances sont 0, 1, 1, 2, 2 et 3. Un chemin minimal est A→B→D→F ; A→C→E→F est également minimal.

Correction du TD 3

L’ordre de visite et l’arbre de parcours changent. L’ensemble des sommets accessibles, la complexité et le fait que chaque sommet soit visité une fois restent invariants.

Correction du TD 4

Le graphe possède trois composantes. La forêt contient un arbre sur {A,B,C,D}, un arbre sur {E,F} et un arbre réduit au sommet isolé G.

Correction du TD 5

Un BFS avec arrêt à la découverte de la cible fournit un chemin minimal non pondéré. Le tableau Parent permet de remonter de la cible vers la source, puis d’inverser le résultat.

Correction du TD 6

Dans un graphe non orienté, chaque arête apparaît dans les deux sens. Le parent est donc toujours un voisin déjà visité. Le triangle contient un cycle, tandis que la chaîne n’en contient pas.

Correction du TD 7

Dans le premier graphe, l’arc C→A atteint un sommet gris : un cycle existe. Dans le second, aucun arc ne pointe vers un sommet gris ; le graphe est acyclique.

Correction du TD 8

Chaque case libre est reliée à ses voisines libres orthogonales. Une case intérieure peut avoir quatre voisins et une case de bord au plus trois. Le BFS est choisi pour minimiser le nombre de déplacements.

Correction du TD 9

Avec les listes, chaque sommet et chaque entrée d’adjacence sont examinés une fois : O(n+m). Avec une matrice, l’algorithme examine n cases pour chacun des n sommets : O(n²).

Correction du TD 10

Travail pratique — Bibliothèque de parcours de graphes

Objectif

Développer une bibliothèque capable d’exécuter DFS et BFS sur une représentation par listes d’adjacence, puis de résoudre plusieurs problèmes classiques.

Fonctionnalités attendues

• ajouter et supprimer des sommets et des arêtes ;

• exécuter un DFS récursif et un DFS itératif ;

• exécuter un BFS et retourner les distances et les parents ;

• reconstruire un chemin entre deux sommets ;

• tester la connexité et lister les composantes connexes ;

• détecter un cycle dans un graphe non orienté ;

• charger un graphe depuis un fichier texte ;

• mesurer le nombre de sommets et d’arêtes examinés.

Organisation recommandée

Étapes de réalisation

1. Implémenter ou réutiliser un TAD Graphe par listes d’adjacence.

2. Écrire les versions DFS et vérifier l’absence de visites multiples.

3. Écrire le BFS avec distances et parents.

4. Ajouter la reconstruction des chemins.

5. Ajouter les composantes connexes et la détection de cycles.

6. Créer des tests unitaires et comparer les ordres obtenus.

7. Mesurer les opérations sur des graphes de tailles croissantes.

Jeux d’essai obligatoires

Grille d’évaluation

Synthèse du chapitre

Glossaire

Auto-évaluation

Fin du chapitre 17 — Parcours de graphes