algorithm
Depth First Search

Introduction à la recherche en profondeur

La recherche en profondeur est un algorithme permettant de parcourir ou de rechercher des structures de données arborescentes ou graphiques. On commence à la racine et explore le plus loin possible le long de chaque branche avant de revenir en arrière. Le mathématicien français Charles Pierre Trémaux, un mathématicien français du XIXe siècle, a étudié une version de la recherche en profondeur pour résoudre les labyrinthes.

La recherche en profondeur est un moyen systématique de trouver tous les sommets accessibles depuis un sommet source. Comme pour la recherche en largeur, DFS traverse un composant connecté d'un graphe donné et définit un spanning tree. L'idée de base de la recherche en profondeur est d'explorer méthodiquement chaque bord. Nous recommençons à partir de différents sommets si nécessaire. Dès que nous découvrons un sommet, DFS commence à l'explorer (contrairement à BFS, qui place un sommet dans une file d'attente pour l'explorer ultérieurement).

Regardons un exemple. Nous allons parcourir ce graphique:

Nous allons parcourir le graphique en suivant ces règles:

• Nous allons commencer par la source.
• Aucun nœud ne sera visité deux fois.
• Les nœuds que nous n'avons pas encore visités seront colorés en blanc.
• Le nœud que nous avons visité, mais qui n'a pas visité tous ses nœuds enfants, sera coloré en gris.
• Les nœuds complètement parcourus seront colorés en noir.

Regardons ça pas à pas:

Nous pouvons voir un mot-clé important. C'est le backedge . Tu peux voir. 5-1 s'appelle backedge. En effet, nous n’avons pas encore fini avec node-1 , donc passer d’un autre noeud au noeud-1 signifie qu’il ya un cycle dans le graphique. Dans DFS, si nous pouvons passer d'un nœud gris à un autre, nous pouvons être certains que le graphique a un cycle. C'est l'un des moyens de détecter un cycle dans un graphique. En fonction du nœud source et de l'ordre des nœuds que nous visitons, nous pouvons identifier n'importe quel bord d'un cycle en tant que backedge . Par exemple: si nous passions à 5 au lieu de 1 , nous aurions découvert 2-1 comme backedge.

Le bord que nous prenons pour passer du nœud gris au nœud blanc est appelé bord d'arbre . Si nous ne conservons que l' arête de l' arborescence et en supprimons d'autres, nous obtiendrons l' arborescence DFS .

Dans un graphique non orienté, si nous pouvons visiter un nœud déjà visité, cela doit être un backedge . Mais pour les graphes dirigés, il faut vérifier les couleurs. Si et seulement si nous pouvons passer d'un nœud gris à un autre nœud gris, cela s'appelle un backedge .

Dans DFS, nous pouvons également conserver des horodatages pour chaque nœud, qui peuvent être utilisés de nombreuses manières (par exemple: tri topologique).

1. Lorsqu'un nœud v passe du blanc au gris, l'heure est enregistrée en d [v] .
2. Lorsqu'un nœud v passe du gris au noir, l'heure est enregistrée dans f [v] .

Ici, d [] signifie temps de découverte et f [] signifie heure de fin . Notre pesudo-code ressemblera à ceci:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

Complexité:

Chaque nœud et chaque arête sont visités une fois. La complexité de DFS est donc O (V + E) , où V désigne le nombre de nœuds et E le nombre d’arêtes.

Applications de la recherche en profondeur d'abord:

• Trouver tous les chemins les plus courts d'une paire dans un graphique non dirigé.
• Cycle de détection dans un graphique.
• Trouver son chemin.
• Tri topologique
• Tester si un graphique est bipartite.
• Trouver un composant fortement connecté.
• Résoudre des puzzles avec une solution.