25 - Graphe : parcours en profondeur
Le parcours en largeur nous a permis de trouver le nombre d'arêtes (ou d'arcs) minimum entre un sommet de départ et tous les autres sommets accesibles dans le graphe. Il permet donc d'obtenir le plus court chemin sur les graphes non pondérés. Cet algorithme utilise une File.
Nous allons voir aujourd'hui le parcours en profondeur qui va nous permettre lui d'obtenir d'autres informations sur la structure du graphe. Cet algorithme utilise une Pile (soit une Pile implémentée, soit la Pile des appels récursifs si on utilise une version récursive)
Attention :cette activité est en deux parties. Aujourd'hui, on découvre l'algorithme et son déroulement. Mais vous aurez du mal à voir à quoi il sert car il est incomplet. La prochaine fois, nous le compléterons et vous parviendrons alors à l'utiliser pour trouver tous les chemins entre deux sommets.
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : les 3 activités sur les Graphes
- Algo : Parcours en profondeur d'un Arbre
- Algo : Parcours en largeur d'un Graphe
Evaluation ✎ : 01-02-03-09-10
Documents de cours : open document ou pdf
1 - Rappel : parcours en profondeur d'un arbre
Nous avons déjà vu la notion de parcours en profondeur sur les arbres.
Nous en avons même vu trois !
- Le parcours préfixe (RGD) : on lit la racine puis on part dans le sous-arbre gauche puis droite.
- Le parcours infixe (GRD) : on part dans le sous-arbre gauche, on lit la racine puis on part dans le sous-arbre droite.
- Le parcours suffixe ou postfixe (GDR) : on part dans le sous-arbre gauche, on part dans le sous-arbre droite puis on lit la racine.
Nous n'allons revoir que le parcours préfixe aujourd'hui mais nous pourrions appliquer les autres également si besoin.
Déroulé :
- (1) on explore la racine A de l'arbre puis
- on part dans le sous-arbre gauche dont la racine est B.
- (2) on explore la racine B de l'arbre puis
- on part dans le sous-arbre gauche dont la racine est D.
- (3) on explore la racine D de l'arbre
- on part dans le sous-arbre droite dont la racine est E.
- (4) on explore la racine E de l'arbre
- on part dans le sous-arbre droite dont la racine est C.
- (5) on explore la racine C de l'arbre puis
- on part dans le sous-arbre gauche dont la racine est F.
- (6) on explore la racine F de l'arbre
- on part dans le sous-arbre droite dont la racine est G.
- (7) on explore la racine G de l'arbre
2 - Parcours en profondeur d'un graphe
Vous allez voir que ce parcours illustre très bien ce qu'on pourrait faire en étant enfermé dans un labyrinthe. On place une marque dans la pièce où on se trouve. Dès qu'on rentre dans une nouvelle salle, on la marque. Si on arrive dans une salle déjà visité que faire ? Simplement retourner en arrière d'un cran et tenter de trouver une salle non visitée à partir de là. Si on n'y trouve pas, on remonte encore d'un cran ect...
Vous allez pouvoir visualiser le principe sur le labyrinthe suivant : on suit un chemin et lorsqu'on atteint un cul de sac ou une case qu'on a déjà exploré, on revient au plus récent embranchement non visité.
Si on avait utilisé un parcours en largeur, nous aurions découvert le labyrinthe sur un rayon de plus en plus grand autour du point de départ.
2.1 Principe du parcours en profondeur dans un graphe
Il s'agit du même principe avec un peu plus de subtilité dans l'exploration car on risque de retomber sur des sommets que nous avons déjà rencontré : il n'y a pas de notion de hierarchie dans un graphe et il peut y avoir des cycles.
On commence par un sommet choisi (S5 dont la liste d'adjacence est par exemple [S1-S9]).
On lit S1 car il le premier sommet dans la liste d'adjacence de S5.
La liste d'adjacence de S1 est [S2-S3-S5].
On lit S2 car il le premier sommet dans la liste d'adjacence de S1.
La liste d'adjacence de S2 est [S1-S3-S4-S6].
On ne lit pas S1 même s'il est le premier dans la liste d'adjacence car ce sommet a déjà été visité.
On passe à S3 et sa liste d'adjancence [S1-S2-S4]...
Pour faire comprendre cela à un système informatique, nous allons utiliser les attributs suivants :
- un attribut couleur pour préciser l'état du sommet lors de l'exploration :
- BLANC : le sommet n'a pas encore été découvert lors de l'exploration
- GRIS : le sommet a été découvert et visité (contrairement au parcours en largeur, la découverte et la première visite sur place se font en même temps)
- NOIR : le sommet a été traité : on a exploré toutes ses arêtes ou ses arcs sortants.
- un attribut parent qui contient le sommet depuis lequel on a découvert ce sommet. VIDE au départ de l'exploration. Seul le sommet de départ gardera cette valeur puisqu'il est le premier.
Voici l'algorithme en français du parcours_en_profondeur :
- Pour chaque sommet u appartenant à l'ensemble S des sommets :
- on place BLANC dans couleur et
- on place VIDE dans parent
- Pour chaque sommet u appartenant à l'ensemble S des sommets :
- Si u est BLANC
- On lance la fonction visiter_en_profondeur sur ce sommet u
Remarque : on ne choisit pas vraiment un sommet de départ : il s'agira simplement du premier sommet obtenu dans l'ensemble des sommets.
Et voici l'algorithme de la fonction visiter_en_profondeur sur ce sommet u :
- On modifie l'attribut couleur de u à GRIS car on va commencer son traitement
- Pour chaque sommet v appartenant à la liste d'adjacence de u :
- Si v est BLANC
- On modifie l'attribut parent de v en y plaçant u
- On lance la fonction visiter_en_profondeur sur ce sommet v
- On modifie l'attribut couleur de u à NOIR puisqu'on a testé toutes ses arêtes ou arcs
2.2 Exemple de déroulement de l'algorithme de parcours en profondeur
On considère le graphe suivant en prenant le sommet 5 comme point de départ : on considéra par l'exemple que les sommets du graphe sont stockés dans la liste suivante :
S5 → S6 → S7 → S8 → S9 → S1 → S2 → S3 → S4
Etape initiale
On place tous les parents à VIDE et tous les noeuds en BLANC.
On commence à itérer sur la liste des sommets, le sommet u sera donc le sommet S5.
Les listes d'adjacence sont placés à proximité des sommets pour plus de facilité de lecture.
Appel de visiter_en_profondeur(S5)
Comme S5 est BLANC, on commence son traitement : on lance l'appel de visiter_en_profondeur(S5).
On le peint en GRIS.
On prend le premier sommet de la liste d'adjacence : S1. Puisqu'il est BLANC, on commence son traitement :
- on impose S1.parent = S5 : on commence ainsi à tracer un arbre de parcours.
- On lance l'appel de visiter_en_profondeur(S1). Il s'agit donc d'un appel récursif.
On voit à droite la création d'un Arbre de parcours.
La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S1)
On peint S1 en GRIS.
On prend le premier sommet de la liste d'adjacence : S2. Puisqu'il est BLANC, on commence son traitement :
- on impose S2.parent = S1 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S2). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S2)
On peint S2 en GRIS.
On prend le premier sommet de la liste d'adjacence : S1. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S3. Puisqu'il est BLANC, on commence son traitement :
- on impose S3.parent = S2 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S3). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S3)
On peint S3 en GRIS.
On prend le premier sommet de la liste d'adjacence : S1. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S2. Puisqu'il est GRIS, on ne fait rien !
On prend le troisième sommet de la liste d'adjacence : S4. Puisqu'il est BLANC, on commence son traitement :
- on impose S4.parent = S3 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S4). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S4)
On peint S4 en GRIS.
On prend le premier sommet de la liste d'adjacence : S2. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S3. Puisqu'il est GRIS, on ne fait rien !
On prend le troisième sommet de la liste d'adjacence : S7. Puisqu'il est BLANC, on commence son traitement :
- on impose S7.parent = S4 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S7). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S7)
On peint S7 en GRIS.
On prend le premier sommet de la liste d'adjacence : S4. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S6. Puisqu'il est BLANC, on commence son traitement :
- on impose S6.parent = S7 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S6). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S6)
On peint S6 en GRIS.
On prend le premier sommet de la liste d'adjacence : S2. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S7. Puisqu'il est GRIS, on ne fait rien !
On prend le troisième sommet de la liste d'adjacence : S8. Puisqu'il est BLANC, on commence son traitement :
- on impose S8.parent = S6 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S8). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S6)
- Appel de visiter_en_profondeur(S8)
Appel de visiter_en_profondeur(S8)
On peint S8 en GRIS.
On prend le premier sommet de la liste d'adjacence : S6. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S9. Puisqu'il est BLANC, on commence son traitement :
- on impose S9.parent = S8 : voir l'arbre ci-dessous.
- On lance l'appel de visiter_en_profondeur(S9). Il s'agit donc d'un appel récursif.
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S6)
- Appel de visiter_en_profondeur(S8)
- Appel de visiter_en_profondeur(S9)
Appel de visiter_en_profondeur(S9)
On peint S9 en GRIS.
On prend le premier sommet de la liste d'adjacence : S5. Puisqu'il est GRIS, on ne fait rien !
On prend le deuxième sommet de la liste d'adjacence : S8. Puisqu'il est GRIS, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S9.
On peint S9 en NOIR.
L'appel à visiter_en_profondeur(S9) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S8)
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S6)
- Appel de visiter_en_profondeur(S8)
Retour à visiter_en_profondeur(S8)
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S8.
On peint S8 en NOIR.
L'appel à visiter_en_profondeur(S8) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S6)
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S6)
Retour à visiter_en_profondeur(S6)
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S6.
On peint S6 en NOIR.
L'appel à visiter_en_profondeur(S6) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S7)
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S7)
Retour à visiter_en_profondeur(S7)
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S7.
On peint S7 en NOIR.
L'appel à visiter_en_profondeur(S7) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S4)
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S4)
Retour à visiter_en_profondeur(S4)
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S4.
On peint S4 en NOIR.
L'appel à visiter_en_profondeur(S4) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S3)
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
Retour à visiter_en_profondeur(S3)
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S3.
On peint S3 en NOIR.
L'appel à visiter_en_profondeur(S3) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S2)
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
- Appel de visiter_en_profondeur(S2)
Retour à l'appel de visiter_en_profondeur(S2)
On reprend avec le sommet suivant non traité dans la liste d'adjacence : S4. Puisqu'il est NOIR, on ne fait rien !
On continue : S6. Puisqu'il est NOIR, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S2.
On peint S2 en NOIR.
L'appel à visiter_en_profondeur(S2) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S1)
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
- Appel de visiter_en_profondeur(S1)
Retour à l'appel de visiter_en_profondeur(S1)
On reprend avec le sommet suivant non traité dans la liste d'adjacence : S3. Puisqu'il est NOIR, on ne fait rien !
On continue : S5. Puisqu'il est GRIS, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S1.
On peint S1 en NOIR.
L'appel à visiter_en_profondeur(S1) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S5)
On voit à droite l'Arbre de parcours. La pile des appels donne :
- Appel de visiter_en_profondeur(S5)
Retour à l'appel de visiter_en_profondeur(S5)
On reprend avec le sommet suivant non traité dans la liste d'adjacence : S9. Puisqu'il est NOIR, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S5.
On peint S5 en NOIR.
L'appel à visiter_en_profondeur(S5) est terminé et elle renvoie None.
On dépile donc et on revient à la boucle sur les sommets du graphes.
Nous avons traité le sommet S5
On passe au même traitement pour S6 mais tous les sommets de sa liste d'adjacence sont NOIR. Du coup, ça va plus vite : on ne fait rien. Comme tous les sommets sont déjà noirs sur cet exemple, on va donc devoir itérer sommet par sommet, même si ici on sait qu'on ne fera plus rien. Mais nous verrons plus bas d'autres exemples où cela sera utile.
A partir de là, toutes les arêtes de tous les sommets ont été explorées. Nous avons donc parcouru l'intégralité du graphe.
On obtient au final :
- Un Arbre si le graphe est connexe ou plusieurs Arbres si le graphe n'est pas connexe (on parle alors de forêt).
- Notre Arbre est d'ailleurs filiforme ici et permettrait de partir du sommet S5 et d'y revenir en passant une seule fois par tous les autres sommets du graphe. On parle donc de cycle hamiltonien (on passe une seule fois par chaque sommet).
3.3 Questions de compréhension
✎ 01° Sur l'Arbre de parcours obtenu, quel est l'enchaînement de sommets obtenu pour aller du sommet S5 au sommet S6 ?
✎ 02° S'agit-il d'un chemin minimum en terme de nombre d'arêtes comme avec le parcours en largeur ?
✎ 03° Regardons si l'ordre des sommets dans les listes d'adjacence a une importante. Réaliser le parcours en profondeur sur ce "nouveau" graphe. Comparer votre Arbre de parcours à l'ancien Arbre.
...CORRECTION...
04° On utilise une fois chaque sommet comme centre de recherches. Combien de fois utilise-t-on les arêtes ?
- On utilise une fois chaque arête
- On utilise deux fois chaque arête
- On utilise trois fois chaque arête
- J'aime ni les arêtes, ni le poisson
...CORRECTION...
On utilise les arêtes dans les deux sens. Donc deux fois.
05° Nous allons chercher la complexité de cet algorithme en prenant comme référence le nombre de fois où on teste si un sommet est BLANC. Notons a le nombre d'arêtes. La complexité de cet algorithme est :
- Logarithmique en fonction de a ?
- Linéaire en fonction de a ?
- Quadratique en fonction de a ?
- Exponentielle en fonction de a ?
...CORRECTION...
Puisqu'on utilise deux fois les arêtes, on peut noter Θ(2a). Comme on ne s'intéresse pas au facteur multiplicatif, on obtient donc Θ(a). La bonne réponse est donc linéaire.
Le coût total d'exécution dépend en réalité du nombre de sommets et du nombre d'arêtes. A cause de la boucle initiale sur les sommets, l'algorithme assure qu'on explore chaque sommet même en cas de graphe non connexe.
On peut donc écrire 𝞗(s+a)
On rappele que pour l'algorithme de parcours en largeur, on écrit simplement 𝞞(s+a) car si le graphe est non connexe, on ne passe pas forcément par tous les sommets et toutes les arêtes.
06° D'autres listes d'adjacences : vous devriez voir qu'on peut avoir un arbre non filiforme même avec un graphe connexe.
...CORRECTION...
07° Est-ce qu'on peut trouver le plus court chemin (en nombre d'arêtes) avec cet algorithme ? A quoi peut-il servir ?
...CORRECTION...
Non : le parcours en profondeur ne permet pas de trouver le plus court chemin en terme d'arêtes ou d'arcs.
Nous allons voir qu'il permet par contre d'apprendre beaucoup de choses sur la forme et la topologie du graphe.
08° Quelle va être la forme de la forêt obtenue avec ce graphe ? (la seule différence vient du fait que les sommets 4 et 7 sont isolés des autres)
...CORRECTION...
Bien entendu avec des graphes non orientés, la seule possibilité d'obtenir un graphe non connexe est que certains sommets soient isolés des autres. C'est donc visible très facilement. Dans les exercices, nous verrons qu'avec les graphes orientés, c'est moins évident à voir sans lancer un parcours en profondeur.
3 - Algorithme de parcours en profondeur
Algorithme du parcours en profondeur
ENTREES
- Un graphe noté g
SORTIE
Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre ou la Forêt du parcours. En réalité ici, on stocke l'arbre directement via les sommets : on leur attribue un parent.
ALGORITHME PARCOURS EN PROFONDEUR
on initialise tous les sommets
POUR chaque sommet u appartenant au graphe g
u.couleur ← BLANC
u.parent ← VIDE
Fin Pour
on lance le traitement des sommets un par un
POUR chaque sommet u appartenant au graphe g
SI u.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été découvert
visiter_en_profondeur(u)
Fin Si
Fin Pour
Renvoyer VIDE (∅)
ALGORITHME de visiter_en_profondeur(u)
u.couleur ← GRIS
POUR chaque sommet v de la liste d'adjacence du sommet u
SI v.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été visité
v.parent ← u.
visiter_en_profondeur(v)
Fin Si
Fin Pour
ici, tous les sommets adjacents ont été tentés
u.couleur ← NOIR
Renvoyer VIDE (∅)
4 - Exercices
Nous allons maintenant travailler sur des graphes non pondérés mais orientés. Plus de chances d'obtenir une forêt de parcours.
✎ 09° Explorer en profondeur ce graphe orienté pour tracer son arbre ou sa forêt de parcours.
...CORRECTION...
✎ 10° Explorer en profondeur ce graphe orienté pour tracer son arbre ou sa forêt de parcours.
...CORRECTION...
5 - FAQ
Rien pour le moment
Activité publiée le 02 05 2021
Dernière modification : 04 05 2021
Auteur : ows. h.