Recherche en profondeur (DFS)

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Parcours d’arbre/de graphe

  • Processus visite tous les nœuds
  • Recherche en profondeur (DFS)
  • Recherche en largeur (BFS)
Structures de données et algorithmes en Python

Recherche en profondeur - arbres binaires

  • En ordre
  • Pré-ordre
  • Post-ordre
Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche
Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel
Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre

  • Ordre : Gauche -> Actuel -> Droite

Représentation graphique du parcours infixe d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en ordre - implémentation

  • Ordre : Gauche -> Actuel -> Droite
def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

Représentation graphique d’un arbre de recherche binaire.

  • Complexité : $O(n)$
    • $n$ -> nombre de nœuds
Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel
Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche
Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours en préordre d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préfixe d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre de recherche binaire.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours en préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre

  • Ordre : Actuel -> Gauche -> Droite

Représentation graphique du parcours préordre d’un arbre binaire de recherche.

Structures de données et algorithmes en Python

Parcours en pré-ordre - implémentation

  • Ordre : Racine -> Gauche -> Droite
  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

Représentation graphique d’un arbre de recherche binaire.

  • Complexité : $O(n)$
    • $n$ -> nombre de nœuds
Structures de données et algorithmes en Python

Post-ordre

  • Ordre : Gauche
Structures de données et algorithmes en Python

Post-ordre

  • Ordre : Gauche -> Droite
Structures de données et algorithmes en Python

Post-ordre

  • Ordre : Gauche -> Droite -> Actuel

  • Complexité : $O(n)$

    • $n$ -> nombre de nœuds
Structures de données et algorithmes en Python

Quand utiliser parcours en ordre, pré-ordre et post-ordre

  • dans l’ordre

    • utilise BST pour obtenir valeurs nœud par ordre croissant

  • pré-ordre

    • créer copies d’un arbre
    • obtenir expressions de préfixe

  • post-ordre

    • supprimer arbres binaires
    • obtenir expressions suffixées
Structures de données et algorithmes en Python

Recherche en profondeur - graphes

  • Les graphes peuvent avoir des cycles
    • besoin de suivre les sommets visités
  • Étapes :
    1. Commencer avec n’importe quel sommet
    2. Ajoute sommet actuel à liste sommets visités
    3. Pour chaque sommet adjacent du nœud actuel
      • S’il a déjà été visité -> l’ignorer
      • S’il n’a pas été visité -> DFS récursif
Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - graphes

Représentation graphique d’une recherche en profondeur dans un graphe.

Structures de données et algorithmes en Python

Recherche en profondeur - implémentation

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)
  • Complexité : $O(V+E)$
    • $V$ -> nombre de sommets
    • $E$ -> nombre d'arêtes
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...