data-structures Depth First Search


Exemple

Depth First Traversal (ou Search) pour un graphique est similaire à Depth First Traversal d'un arbre. Le seul problème ici est que, contrairement aux arbres, les graphiques peuvent contenir des cycles, nous pouvons donc revenir au même nœud. Pour éviter de traiter un nœud plusieurs fois, nous utilisons un tableau booléen visité.

L'algorithme ci-dessous présente les étapes pour la traversée de graphe en utilisant DFS:

Algorithme DFS (v);

Entrée : Un sommet v dans un graphique

Sortie : un étiquetage des arêtes comme arêtes de “découverte” et “backedges”

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

Illustration DFS

entrer la description de l'image ici