Algo Graphe Profondeur

Identification

Infoforall

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 !

  1. Le parcours préfixe (RGD) : on lit la racine puis on part dans le sous-arbre gauche puis droite.
  2. Le parcours infixe (GRD) : on part dans le sous-arbre gauche, on lit la racine puis on part dans le sous-arbre droite.
  3. 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.

Arbre question 2

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é.

Vidéo réalisée par le contributeur Purpy Pupple et tirée de l'article Wikipedia suivant parours en profondeur

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]...

Animation du parcours
CLIQUEZ SUR L'IMAGE POUR LANCER L'ANIMATION

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 :
    1. BLANC : le sommet n'a pas encore été découvert lors de l'exploration
    2. 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)
    3. 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 :

  1. Pour chaque sommet u appartenant à l'ensemble S des sommets :
    • on place BLANC dans couleur et
    • on place VIDE dans parent

    Remarque : on ne choisit pas vraiment un sommet de départ : il s'agira simplement du premier sommet obtenu dans l'ensemble des sommets.

  2. 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

Et voici l'algorithme de la fonction visiter_en_profondeur sur ce sommet u :

  1. On modifie l'attribut couleur de u à GRIS car on va commencer son traitement
  2. 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
  3. 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 :

S5S6S7S8S9S1S2S3S4

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.

Image montrant la configuration initiale

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.
Etape 2

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.
Etape 2

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 !

Etape 2

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.
Etape 2

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 !

Etape 6

On prend le deuxième sommet de la liste d'adjacence : S2. Puisqu'il est GRIS, on ne fait rien !

Etape 7

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.
Etape 8

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 !

Etape 9

On prend le deuxième sommet de la liste d'adjacence : S3. Puisqu'il est GRIS, on ne fait rien !

Etape 10

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.
Etape 11

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 !

Etape 12

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.
Etape 13

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 !

Etape 14

On prend le deuxième sommet de la liste d'adjacence : S7. Puisqu'il est GRIS, on ne fait rien !

Etape 15

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.
Etape 16

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 !

Etape 17

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.
Etape 18

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 !

Etape 19

On prend le deuxième sommet de la liste d'adjacence : S8. Puisqu'il est GRIS, on ne fait rien !

Etape 20

Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S9.

On peint S9 en NOIR.

Etape 21

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.

Etape 22

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.

Etape 23

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.

Etape 24

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.

Etape 25

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.

Etape 26

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 !

Etape 27

On continue : S6. Puisqu'il est NOIR, on ne fait rien !

Etape 28

Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S2.

On peint S2 en NOIR.

Etape 29

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 !

Etape 30

On continue : S5. Puisqu'il est GRIS, on ne fait rien !

Etape 31

Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S1.

On peint S1 en NOIR.

Etape 32

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 !

Etape 33

Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S5.

On peint S5 en NOIR.

Etape 34

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.

Animation du parcours
CLIQUEZ SUR L'IMAGE POUR LANCER L'ANIMATION

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).
Arbre obtenu avec ce parcours

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.

Question 3

...CORRECTION...

Correction 3

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 convexe.

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 convexe, 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.

Question 6

...CORRECTION...

Correction 6

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)

Question 8

...CORRECTION...

Correction 8

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.

Graphe de l'exercice 9
Tiré de Algorithmique, Cormen-Leiserson-Rivest-Stein

...CORRECTION...

Correction 9

✎ 10° Explorer en profondeur ce graphe orienté pour tracer son arbre ou sa forêt de parcours.

Graphe de l'exercice 10
Tiré de Algorithmique, Cormen-Leiserson-Rivest-Stein

...CORRECTION...

Correction 10

5 - FAQ

Rien pour le moment

Nous rajouterons une couche d'information la prochaine fois et nous verrons ainsi comment détecter la présence d'un cycle dans un graphe complexe : vous n'avez peut-être pas envie de créer un processus qui peut potentiellement tourner en boucle, si ?

Activité publiée le 02 05 2021
Dernière modification : 04 05 2021
Auteur : ows. h.