Parcours en profondeur (DFS)

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Parcours d’arbres/graphes

• Processus de visite de tous les nœuds
• Parcours en profondeur (DFS)
• Parcours en largeur (BFS)

Parcours en profondeur - arbres binaires

• Infixe
• Préfixe
• Postfixe

Parcours infixe

• Ordre : Gauche

Parcours infixe

• Ordre : Gauche -> Courant

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe

• Ordre : Gauche -> Courant -> Droite

Parcours infixe - implémentation

• Ordre : Gauche -> Courant -> 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

• Complexité : $O(n)$
  • $n$ -> nombre de nœuds

Parcours préfixe

• Ordre : Courant

Parcours préfixe

• Ordre : Courant -> Gauche

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe

• Ordre : Courant -> Gauche -> Droite

Parcours préfixe - 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

• Complexité : $O(n)$
  • $n$ -> nombre de nœuds

Postfixe

• Ordre : Gauche

Postfixe

• Ordre : Gauche -> Droite

Postfixe

• Ordre : Gauche -> Droite -> Courant

• Complexité : $O(n)$

  • $n$ -> nombre de nœuds

Quand utiliser infixe, préfixe et postfixe

• Infixe

  • utiliser un ABR pour obtenir les valeurs des nœuds par ordre croissant

• Préfixe

  • copier un arbre
  • obtenir des expressions préfixées

• Postfixe

  • supprimer des arbres binaires
  • obtenir des expressions postfixées

Parcours en profondeur - graphes

• Les graphes peuvent avoir des cycles
  • il faut suivre les sommets visités
• Étapes :
  1. Partir de n’importe quel sommet
  2. Ajouter le sommet courant à la liste des visités
  3. Pour chaque sommet adjacent au courant
     • S’il a été visité -> l’ignorer
     • S’il n’a pas été visité -> appliquer récursivement le DFS

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours en profondeur - graphes

Parcours 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

Passons à la pratique !

Structures de données et algorithmes en Python