Depth first Search ou Depth first traversal est un algorithme récursif permettant de rechercher tous les sommets d’un graphe ou d’une structure de données arborescente. La traversée signifie visiter tous les nœuds d’un graphique.

algorithme de recherche en profondeur

Une implémentation DFS standard place chaque sommet du graphe dans l’une des deux catégories suivantes:

1. visité
2. Non visité

le but de l’algorithme est de marquer chaque sommet comme visité tout en évitant les cycles.,

l’algorithme DFS fonctionne comme suit:

1. commencez par placer l’un des sommets du graphe au-dessus d’une pile.
2. prenez l’élément supérieur de la pile et ajoutez-le à la liste visitée.
3. créez une liste des nœuds adjacents de ce sommet. Ajoutez ceux qui ne sont pas dans la liste visitée en haut de la pile.
4. continuez à répéter les étapes 2 et 3 jusqu’à ce que la pile soit vide.

exemple de recherche de profondeur d’abord

voyons comment l’algorithme de recherche de profondeur d’abord fonctionne avec un exemple. Nous utilisons un graphe non orienté avec 5 sommets.,

Nous partons du sommet 0, l’algorithme DFS commence par le mettre dans la liste visitée et mettre tous ses sommets adjacents dans la pile.

Ensuite, visite de l’élément au sommet de la pile c’est à dire 1 et aller à ses nœuds adjacents. Puisque 0 a déjà été visité, nous visitons 2 à la place.,

Vertex 2 a un inconnu sommet adjacent à 4, donc nous ajoutons que, pour le haut de la pile et de le visiter.

Après avoir visité le dernier élément 3, Il n’a pas de nœuds adjacents non visités, nous avons donc terminé la première traversée de profondeur du graphique.,

Pseudocode DFS (implémentation récursive)

le pseudocode pour DFS est illustré ci-dessous. Dans la fonction init (), notez que nous exécutons la fonction DFS sur chaque nœud. En effet, le graphique peut avoir deux parties déconnectées différentes, donc pour s’assurer que nous couvrons chaque sommet, nous pouvons également exécuter l’algorithme DFS sur chaque nœud.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

implémentation DFS en Python, Java et C/c++

le code de L’algorithme de recherche en profondeur avec un exemple est illustré ci-dessous. Le code a été simplifié afin que nous puissions nous concentrer sur l’algorithme plutôt que d’autres détails.

la Complexité du parcours en Profondeur d’Abord de Recherche

Le temps de la complexité de l’algorithme DFS est représenté sous la forme de O(V + E), où V est le nombre de nœuds et E est le nombre d’arêtes.

la complexité spatiale de l’algorithme estO(V).,

l’Application de l’Algorithme DFS

1. Pour trouver le chemin d’accès
2. Pour tester si le graphe est biparti
3. Pour trouver les composantes fortement connexes d’un graphe
4. Pour la détection de cycles dans un graphe