DFS (Depth First Traversal) dans la structure de données : qu'est-ce que c'est, la commande et les applications

Signification de DFS dans la structure de données

DFS dans Data Structure, également connu sous le nom de parcours en profondeur d'abord, est un algorithme récursif principalement utilisé pour rechercher tous les sommets d'un graphe ou d'une structure de données arborescente. La traversée est la visite de chaque nœud d'un graphe. L'algorithme commence à partir du nœud racine (qui peut être un nœud arbitraire en tant que nœud racine dans un graphe) et va aussi loin que possible le long de chaque branche avant de revenir en arrière.

L'idée est de commencer à partir de la racine ou du nœud arbitraire et de garder le nœud marqué. Après cela, vous devez vous déplacer vers le nœud adjacent qui n'est pas marqué et continuer cette boucle jusqu'à ce qu'il n'y ait plus de nœud adjacent non marqué. Ensuite, revenez en arrière et examinez les autres nœuds qui ne sont pas marqués et traversez-les. La dernière étape consiste à imprimer les nœuds dans le chemin.

Algorithme

Formulez une fonction récursive qui prendra l'index du nœud et un tableau visité.

1. Conservez le nœud actuel marqué comme visité, puis imprimez-le.
2. Parcourez toutes les notes adjacentes et celles non marquées et appelez la fonction récursive avec l'index du nœud adjacent.

Explorez nos cours populaires de génie logiciel

Propriétés

L'analyse du temps et de l'espace dans le DFS en Data Structure varie selon son domaine d'application. Théoriquement, DFS est principalement utilisé pour parcourir un graphe complet et prend un temps O(|V|+|E|) où |V| représente le nombre de sommets et |E| représente le nombre d'arêtes. Ce graphique est linéaire.

Dans ces applications, l'espace O(|V|) est également utilisé en dernier recours pour conserver la pile de sommets stockés sur le chemin de recherche et l'ensemble des sommets déjà visités. Par conséquent, le réglage des limites temporelles et spatiales est similaire à la recherche en largeur d'abord. Ici, les deux algorithmes utilisés sont moins dépendants de leur complexité et plus des différentes caractéristiques des ordres de sommets produits par les deux algorithmes.

En ce qui concerne les applications de DFS dans la structure de données liées à des domaines spécifiques, comme la recherche de solutions dans l'exploration Web ou l'IA, le graphique qui nécessite une traversée peut être trop important pour être visité dans son intégralité. Dans de tels cas, la recherche n'est exécutée que sur une profondeur restreinte ; en raison de ressources limitées, comme l'espace disque ou la mémoire. Les structures de données ne sont généralement pas utilisées pour suivre l'ensemble de tous les sommets visités précédemment. Une recherche effectuée à une profondeur restreinte rend toujours le temps linéaire lorsqu'il s'agit de l'unité d'arêtes et de sommets étendus.

Cependant, rappelez-vous que ce nombre n'a pas la même taille que le graphe entier puisque certains des sommets peuvent être recherchés plusieurs fois et d'autres non recherchés.

Dans de tels cas, DFS se tourne également vers des méthodes heuristiques pour sélectionner une branche plus prometteuse. Enfin, lorsque la limite de profondeur appropriée ne peut être déterminée, a priori, un approfondissement itératif DFS est appliqué de manière répétée via une séquence de limites croissantes.

Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Algorithme de recherche en profondeur

Chaque sommet d'un graphe dans une implémentation DFS standard est divisé en deux catégories :

1. Non visité
2. A visité

L'algorithme est utilisé pour localiser chaque sommet et les marquer comme visités et en même temps éviter les cycles.

Voici comment fonctionne l'algorithme DFS :

1. Mettez n'importe quel sommet particulier du graphe sur une pile.
2. L'élément en haut de la pile doit être ajouté à la liste visitée.
3. Faites une liste des nœuds adjacents de ce sommet et ajoutez ceux qui ne figurent pas dans la liste visitée en haut de la pile.
4. Continuez à répéter les étapes précédentes jusqu'à ce que la pile se vide.

Commande DFS

Ordres des sommets : il existe quatre façons d'ordonner linéairement les sommets d'un graphe ou d'un arbre dans DFS :

1. La liste des sommets organisés selon la manière dont ils ont été visités en premier par l'algorithme DFS est connue sous le nom de pré-commande. C'est une façon concise de décrire la progression de la recherche.
2. La liste des sommets dans l'ordre dans lequel ils ont été visités en dernier par l'algorithme est appelée post-ordre.
3. La liste des sommets dans l'ordre inverse de leur première visite est un pré-ordre inverse. Par conséquent, il ne doit pas être confondu avec le post-commande.
4. La liste des sommets dans l'ordre inverse de leur dernière visite est un post-ordre inverse. Il ne faut pas confondre avec une pré-commande.

De plus, il existe un ordre dans l'ordre et un ordre dans l'ordre inverse pour les arbres binaires.

Depth First Search ou DFS pour un graphique

Le DFS pour un graphe est presque le même que le DFS pour un arbre. La seule différence est que les graphes peuvent avoir des cycles, contrairement aux arbres. Un nœud peut être visité plusieurs fois et pour éviter de traiter le nœud, un tableau booléen visité est utilisé.

Résultat d'une première recherche en profondeur

La recherche en profondeur d'abord est plus facilement représentée en termes d'arbre couvrant des sommets qui sont déjà atteints dans la recherche. Sur la base de cet arbre couvrant, les arêtes du graphe d'origine sont divisées en trois classes : les arêtes avant où le nœud de l'arbre est pointé vers l'un de ses descendants, les arêtes arrière où le nœud est pointé vers l'un de ses ancêtres, et les arêtes croisées , qui n'effectue aucune des fonctions précédentes.

Applications de la première traversée en profondeur (DFS)

La recherche en profondeur d'abord est utilisée dans les algorithmes suivants en tant que bloc de construction :

• Recherche de composants connectés.
• Recherche de composants connectés à 2 (sommets ou arêtes).
• Trouver les ponts du graphe.
• Trouver 3 composants connectés (sommet ou arête).
• Tri topologique.
• Trouver des composants qui sont fortement connectés.
• Savoir si une espèce est semblable à telle ou telle espèce dans un arbre phylogénétique.
• Test de planéité.
• Produire des mots pour déterminer l'ensemble limite de n'importe quel groupe.
• Résoudre des énigmes qui n'ont qu'une seule solution, comme des labyrinthes.
• Génération labyrinthe .
• Recherche de bi-connectivité dans les graphes.

Pseudocode DFS et implémentation en Python

La fonction init() est exécutée sur chaque nœud dans le pseudocode ci-dessous pour s'assurer que tous les sommets sont visités. Ceci est particulièrement important car les graphiques peuvent avoir diverses zones déconnectées.

Voici le pseudo-code :

DFS(G, u)

u.visited = true

pour chaque v ∈ G.Adj[u]

si v.visité == faux

DFS(G,v)

init() {

Pour chaque u ∈ G

u.visited = false

Pour chaque u ∈ G

DFS(G, u)

}

Voici l'implémentation DFS en Python :

graphique = {

'5' : ['3′,'7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'sept' : []

}

visité = set()

def dfs(visited, graph, node):

si le nœud n'est pas visité :

impression (noeud)

visité.add(nœud)

pour le voisin dans le graphe[nœud] :

dfs(visité, graphe, voisin)

print("Voici le DFS :")

dfs(visité, graphique, '5')

Production:

C'est le DFS : 5

Explorez nos cours populaires de génie logiciel

La complexité de Depth First Search

John Reif a exploré la complexité informatique de Depth First Search. Pour être précis, dans un graphe, le fait donné est G, soit O l'ordre standard déterminé par l'algorithme DFS répétitif. G représente le graphique et O représente la sortie de classement de l'algorithme DFS redondant. Cette sortie est connue sous le nom de classement DFS lexicographique.

Conclusion

L'objectif principal de l'algorithme DFS est de visiter chaque sommet qui évite les cycles dans les graphes cibles. Si vous souhaitez vous impliquer dans des implémentations avancées d'opérations de recherche ou d'opérations de commande, vous devez absolument envisager de suivre un cours premium et holistique sur la recherche en profondeur et la structure des données.

upGrad propose des cours DFS de haut niveau, tels que le Master of Science en informatique et la spécialisation en Big Data .

Si vous avez du mal à passer à l'étape suivante et que vous recherchez des conseils d'experts, upGrad Mentorship cherche à vous proposer des sessions individuelles avec les meilleurs conseillers en carrière et experts du secteur.