11.2. Depth-First Search

L'algorithme de recherche en profondeur qui a été décrit auparavant reste entièrement valable pour un graphe orienté.

Pour le graphe de la figure 11.1, l'arbre de parcours est illustré à la figure 11.2 et donne l'ordre de parcours suivant:

A F E D B G J K L M C H I

On peut distinguer trois types de liaisons dans cet arbre de parcours :

• les liaisons "en haut" vers un sommet ancêtre (DF ou LG),
• les liaisons "en bas" vers un sommet descendant (JK, JM,
• les liaisons "en travers" vers un sommet qui n'est ni ancêtre ni descendant (GE, HG).

Comme pour les graphes non-orientés, on est intéressé par les propriétés de connectivité. On veut être capable de répondre à des questions du genre:

• Y a-t-il un chemin orienté du sommet x vers le sommet y ?

• Quels sont les sommets accessibles à partir du sommet x ?

• Y a-t-il un chemin de x vers y et un chemin de y vers x ?

On obtient les réponses à ces diverses questions en modifiant l'algorithme de "depth-first search" de différentes manières.

11.3. Fermeture transitive

Table des matières.

Site Hosting: Bronco