Parcours en profondeur d'un graphe

Le parcours en profondeur d'un graphe est un algorithme de parcours le plus souvent récursif et utilisant un tableau de marque.

[modifier] Principe

Cet algorithme utilise un tableau de marque, il s'agit d'un tableau de booléens dont la taille est égale à l'ordre du graphe. Il est initialisé à faux.

Supposons que l'on commence à parcourir à partir d'un sommet s donné. On parcours tous les successeurs de s. Si le successeur n'est pas marqué, on appelle récursivement la fonction sur le successeur.

Fig. 1: Exemple de graphe

Fig. 2: Arbre généré par le parcours profondeur du graphe de la figure 1.

Réalisons le parcours profondeur du graphe de la figure 1.

• On choisit le sommet n°1 comme sommet de départ, on le marque.
• On parcours les successeurs de 1 2 n'est pas marqué, on le choisit.
  • On marque 2.
  • On parcours les successeurs de 2: 3 n'est pas marqué, on le choisit.
    • On marque 3.
    • On parcours les successeurs de 3: 4 n'est pas marqué, on le choisit.
      • On marque 4.
      • 4 n'a pas de successeurs.
    • On continue le parcours des successeurs de 3: 6 n'est pas marqué, on le choisit.
      • On marque 6.
      • On parcours les successeurs de 6: 5 n'est pas marqué, on le choisit.
        • On marque 5.
        • 4 est un successeur de 5 mais il est marqué, on ne le choisit donc pas.
        • 4 n'a plus de successeur non-marqué.
      • 6 n'a plus de successeurs non-marqué.
    • 3 n'a plus de successeurs non-marqué.
  • On continue le parcours des successeurs de 2: 7 n'est pas marqué, on le choisit.
    • On marque 7.
    • 7 n'a pas de successeurs.
  • On continue le parcours des successeurs de 2: 8 n'est pas marqué, on le choisit.
    • On marque 8.
    • 8 n'a pas de successeurs.
  • 2 n'a plus de successeurs non-marqué.
• 1 n'a plus de successeurs non-marqué.

On peut représenter le parcours profondeur par la figure n°2.

[modifier] Spécifications

L'algorithme qui suit réalise un parcours profondeur du graphe g à partir du sommet som_depart. Il affiche les sommets lors de la rencontre préfixe puis suffixe.

[modifier] Implémentation

[modifier] C

void parcours_profondeur(t_graphe_s g, unsigned int som_depart)
{
     int *marque,i;
     marque=malloc(sizeof(int)*g.ordre);
     for(i=0;i<g.ordre;i++)
        marque[i]=0;

        
     printf("\tRencontre prefixe de %d\n",som_depart);
     parcours_profondeur_rec(g,som_depart,marque);
     printf("\tRencontre suffixe de %d\n",som_depart);
     free(marque);
     printf("\n");
}
void parcours_profondeur_rec(t_graphe_s g, unsigned int s, int *marque)
{
     unsigned int i;
     marque[s]=1;
     for (i=0;i<g.ordre;i++)
     {
         if (*(g.adj+s*g.ordre+i)!=0.)
            if(!marque[i])
            {
               printf("\tRencontre prefixe de %d\n",i);
               parcours_profondeur_rec(g,i,marque);
               printf("\tRencontre suffixe de %d\n",i);
            }
     }
}

[modifier] Applications

[modifier] Connexité

Si le graphe n'est pas orienté, un simple parcours en profondeur permet de déterminer si le graphe est connexe. Si tous les sommets n'ont pas été marqué à la fin du parcours en profondeur, alors le graphe n'est pas connexe.