Exploration d'un graphe en profondeur

Introduction

Ce Td a pour but la manipulation de graphe orientés représentés sous la forme de tableaux de listes de successeurs. Le nombre de sommets du graphe sera fixé par une constante Nb. Les graphes manipulés n'admettront pas de flèches de la forme x->x, où x est un sommet. On utilisera les types suivants pour la manipulation de ces graphes :

type
        pt= ^Boite;
        Boite= record
                       num: 1..Nb;
                       suivant:pt;
               end;
        Graphe= array[1..Nb] of pt;

Interface

La saisie des données et l'affichage des résultats peuvent se faire dans la fenêtre Texte et la fenêtre Drawing. Des procédures permettant la saisie et l'affichage simultanés d'un graphe dans la fenêtre Drawing, l'affichage d'un graphe existant dans la fenêtre Drawing ou dans la fenêtre Texte, peuvent être récupérées de la façon suivante. Si vous êtes sous Mac ou PC vous pouvez récupérer le fichier à compléter GrapheIncomplet.p et les unités qu'il utilise : Click.p et Affichage.p et construire le fichier project ou .dpr en conséquence. Vous pouvez ne regarder que les parties "interface" des unités. Si vous êtes sous station ou si vous préferer travailler pour ce Td avec un seul fichier, vous pouvez récupérer le seul fichier à compléter Graphe.p. Il n'est pas indispensable de travailler avec des unités. Ceci pourra vous être utile lorsque vous réaliserez le projet. Après installation, lancez le programme (incomplet). On effectue la saisie des sommets en cliquant dans la fenêtre graphique (le nombre de sommets est fixé). Le sommets sont numérotés par défaut 1,2 ... . On clique ensuite sur les successeurs du sommet 1 en terminant par clic sur une zone blanche, puis sur les successeurs du sommet 2, etc. Chaque flèche saisie est insérée en tête de la liste des successeurs.

Description du travail demandé

• Ecrire une procédure Parcours permettant d'explorer un graphe en profondeur. Cette procédure fera appel à la procédure récursive Tremaux (voir cours de Jean Berstel ou le poly). On fera afficher les sommets dans l'ordre qui correspond au début de l'exploration (début de la procédure Tremaux). On utilisera un tableau couleur qui indique pour chaque sommet sa couleur prise dans trois valeurs : blanc, gris ou noir. Un sommet est blanc si son exploration n'a pas commencé, il est gris pendant l'exploration et devient noir au moment où celle-ci se termine.
• Modifiez ce qui précède pour construire le graphe appelé forêt recouvrante qui est formé des même sommets et des flèches directes (ou flèches de l'arbre). Lors d'une exploration, les flèches d'un graphe orienté peuvent être directes, descendantes, tranverses, ou retour (arrières). Sur le graphe ci-dessous, on effectue une exploration en suivant l'ordre donné par les numéros des sommets. Les arcs directs obtenus sont en vert, les arcs descendants en bleu, les arcs retour en rouge et les arcs transverses en noir.
  
• Montrez qu'il existe un circuit si et seulement si il existe un arc retour. Modifiez l'exploration pour pouvoir tester si un graphe est ou non sans circuit. On pourra faire afficher un arc retour s'il en existe. On pourra faire afficher un circuit s'il en existe un.
• On effectue maintenant une exploration du graphe G en faisant afficher les sommets dans l'ordre qui correspond à la fin de leur procédure Tremaux (l'ordre de la fin de l'exploration). On renverse cet ordre et on appelle l'ordre ainsi obtenu NumFinInverse. On calcule le graphe retourné de G, noté Gr, obtenu en renversant le sens des flèches. On effectue ensuite l'exploration de Gr en suivant l'ordre NumFinInverse sur les sommets dans la procédure Parcours. Montrer que la forêt obtenue lors de cette deuxième exploration est telle que ses arborescences sont les composantes fortement connexes du graphe. Programmez ainsi le calcul des composantes fortement connexes.

Une solution apparaîtra ici.

Une application

L'exploration en profondeur peut être utilisée pour des graphes non orientés. Dans ce cas certaines simplifications apparaissent : les arcs ne peuvent plus être que directs ou retour. Une application consiste à modéliser un labyrinthe sous forme de graphe non orienté et à programmer le calcul d'un chemin de sortie du labyrinthe. On affichera par exemple un chemin (s'il en existe un) allant de la case 1 à la case n^2, où n=5, pour un labyrinthe du même type que celui donné ci-dessous:

N'oubliez pas de :