Recherche en profondeur d'abord en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons explorer la recherche en profondeur d'abord en Java.

La recherche en profondeur d'abord (DFS) est un algorithme de parcours utilisé pour les structures de données Tree et Graph. La recherche en profondeur d'abord va en profondeur dans chaque branche avant de passer à l'exploration d'une autre branche .

Dans les sections suivantes, nous examinerons d'abord l'implémentation d'un arbre, puis d'un graphique.

Pour voir comment implémenter ces structures en Java, jetez un œil à nos précédents tutoriels sur Binary Tree and Graph.

2. Recherche en profondeur dans l’arbre

Il existe trois ordres différents pour parcourir une arborescence à l'aide de DFS:

  1. Précommande Traversal
  2. Traversée en ordre
  3. Traversée post-commande

2.1. Précommande Traversal

Dans le parcours de précommande, nous traversons d'abord la racine, puis les sous-arbres gauche et droit.

Nous pouvons simplement implémenter le parcours de précommande en utilisant la récursivité :

  • Visiter le nœud actuel
  • Traverser le sous-arbre gauche
  • Traverser le sous-arbre droit
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Nous pouvons également implémenter le parcours de précommande sans récursivité.

Pour implémenter un parcours de pré-commande itératif, nous aurons besoin d'une pile , et nous passerons par ces étapes:

  • Poussez la racine dans notre amorce
  • Tant que la pile n'est pas vide
    • Pop noeud actuel
    • Visiter le nœud actuel
    • Poussez l' enfant droit , puis l' enfant gauche pour empiler
public void traversePreOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(!stack.isEmpty()) { current = stack.pop(); visit(current.value); if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } }

2.2. Traversée en ordre

Pour une traversée dans l'ordre, nous traversons d'abord le sous-arbre gauche, puis la racine, puis enfin le sous-arbre droit .

La traversée en ordre pour un arbre de recherche binaire signifie la traversée des nœuds dans l'ordre croissant de leurs valeurs.

Nous pouvons simplement implémenter la traversée en ordre en utilisant la récursivité:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); visit(node.value); traverseInOrder(node.right); } }

Nous pouvons également implémenter le parcours inorder sans récursivité :

  • Pousser racine noeud s tack
  • Alors que le bord n'est pas vide
    • Continuez à pousser l' enfant gauche sur la pile, jusqu'à ce que nous atteignions l'enfant le plus à gauche du nœud actuel
    • Visiter le nœud actuel
    • Poussez l' enfant droit sur la pile
public void traverseInOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(! stack.isEmpty()) { while(current.left != null) { current = current.left; stack.push(current); } current = stack.pop(); visit(current.value); if(current.right != null) { current = current.right; stack.push(current); } } }

2.3. Traversée post-commande

Enfin, dans le parcours de post-ordre, nous traversons le sous-arbre gauche et droit avant de traverser la racine .

Nous pouvons suivre notre précédente solution récursive :

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); visit(node.value); } }

Ou, nous pouvons également implémenter la traversée de post-ordre sans récursivité :

  • Pousser le nœud racine dans s tack
  • Alors que le bord n'est pas vide
    • Vérifiez si nous avons déjà traversé le sous-arbre gauche et droit
    • Sinon, poussez l' enfant droit et l' enfant gauche sur la pile
public void traversePostOrderWithoutRecursion() { Stack stack = new Stack(); Node prev = root; Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.peek(); boolean hasChild = (current.left != null || current.right != null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (!hasChild || isPrevLastChild) { current = stack.pop(); visit(current.value); prev = current; } else { if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }

3. Recherche en profondeur du graphique en premier

La principale différence entre les graphiques et les arbres est que les graphiques peuvent contenir des cycles .

Donc pour éviter de chercher par cycles, nous marquerons chaque nœud lorsque nous le visiterons.

Nous verrons deux implémentations pour graph DFS, avec récursivité et sans récursivité.

3.1. Graphique DFS avec récursivité

Tout d'abord, commençons simplement avec la récursivité:

  • Nous allons commencer à partir d'un nœud donné
  • Marquer le nœud actuel comme visité
  • Visiter le nœud actuel
  • Traverser les sommets adjacents non visités
public void dfs(int start) { boolean[] isVisited = new boolean[adjVertices.size()]; dfsRecursive(start, isVisited); } private void dfsRecursive(int current, boolean[] isVisited) { isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) dfsRecursive(dest, isVisited); } }

3.2. Graphique DFS sans récursivité

Nous pouvons également implémenter graph DFS sans récursivité. Nous allons simplement utiliser une pile :

  • Nous allons commencer à partir d'un nœud donné
  • Pousser le nœud de démarrage dans la pile
  • Alors que la pile n'est pas vide
    • Marquer le nœud actuel comme visité
    • Visiter le nœud actuel
    • Pousser les sommets adjacents non visités
public void dfsWithoutRecursion(int start) { Stack stack = new Stack(); boolean[] isVisited = new boolean[adjVertices.size()]; stack.push(start); while (!stack.isEmpty()) { int current = stack.pop(); isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) stack.push(dest); } } }

3.4. Tri topologique

Il existe de nombreuses applications pour la recherche en profondeur de graphe. L'une des applications les plus connues de DFS est le tri topologique.

Le tri topologique pour un graphe orienté est un ordre linéaire de ses sommets de sorte que pour chaque arête, le nœud source précède la destination.

Pour obtenir un tri topologique, nous aurons besoin d'un simple ajout au DFS que nous venons d'implémenter:

  • Nous devons conserver les sommets visités dans une pile car le tri topologique est les sommets visités dans un ordre inversé
  • Nous ne poussons le nœud visité dans la pile qu'après avoir traversé tous ses voisins
public List topologicalSort(int start) { LinkedList result = new LinkedList(); boolean[] isVisited = new boolean[adjVertices.size()]; topologicalSortRecursive(start, isVisited, result); return result; } private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) { isVisited[current] = true; for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) topologicalSortRecursive(dest, isVisited, result); } result.addFirst(current); }

4. Conclusion

Dans cet article, nous avons discuté de la recherche en profondeur d'abord pour les structures de données Tree et Graph.

Le code source complet est disponible sur GitHub.