Recherche en largeur (BFS)

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Recherche en largeur - arbres binaires

  • Commence depuis racine
  • Visite chaque nœud de chaque niveau

Représentation graphique d’une recherche en largeur d’abord sur un arbre de recherche binaire.

Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

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

  • visited_nodes :
  • bfs_queue :
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)

      while not bfs_queue.empty():

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

  • visited_nodes :
  • bfs_queue : 65
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()

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

  • visited_nodes :
  • bfs_queue :
  • current_node : 65
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)

        if current_node.left:

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

  • visited_nodes : 65
  • bfs_queue :
  • current_node : 65
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)

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

  • visited_nodes : 65
  • bfs_queue : 20
  • current_node : 65
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65
  • bfs_queue : 20, 70
  • current_node : 65
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65
  • bfs_queue : 70
  • current_node : 20
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20
  • bfs_queue : 70
  • current_node : 20
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20
  • bfs_queue : 70, 10
  • current_node : 20
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20
  • bfs_queue : 70, 10, 22
  • current_node : 20
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20
  • bfs_queue : 10, 22
  • current_node : 70
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70
  • bfs_queue : 10, 22
  • current_node : 70
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70
  • bfs_queue : 10, 22, 68
  • current_node : 70
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70
  • bfs_queue : 10, 22, 68, 75
  • current_node : 70
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10
  • bfs_queue : 22, 68, 75
  • current_node : 10
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10
  • bfs_queue : 68, 75
  • current_node : 22
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10, 22
  • bfs_queue : 68, 75
  • current_node : 22
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10, 22, 68
  • bfs_queue : 75
  • current_node : 68
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10, 22, 68
  • bfs_queue :
  • current_node : 75
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

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

  • visited_nodes : 65, 20, 70, 10, 22, 68, 75
  • bfs_queue :
  • current_node : 75
Structures de données et algorithmes en Python

Recherche en largeur - arbres binaires

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)
    return visited_nodes
  • Complexité : $O(n)$

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

  • visited_nodes : 65, 20, 70, 10, 22, 68, 75
  • bfs_queue :
  • current_node : 75
Structures de données et algorithmes en Python

Recherche en largeur - graphes

  • Les graphes peuvent avoir des cycles
    • Vérifier si les sommets ont déjà été visités
Structures de données et algorithmes en Python

Recherche en largeur - graphes

def bfs(graph, initial_vertex):

  visited_vertices = []

  bfs_queue = queue.SimpleQueue()

  bfs_queue.put(initial_vertex)

  visited_vertices.append(initial_vertex)

  while not bfs_queue.empty():

    current_vertex = bfs_queue.get()

    for adjacent_vertex in graph[current_vertex]:

      if adjacent_vertex not in visited_vertices:

        visited_vertices.append(adjacent_vertex)

        bfs_queue.put(adjacent_vertex)

  return visited_vertices
  • Complexité : $O(V+E)$
    • $V$ -> nombre de sommets
    • $E$ -> nombre d'arêtes
Structures de données et algorithmes en Python

Recherche en largeur - graphes

Représentation graphique de la recherche en largeur d’abord sur un graphe.

Structures de données et algorithmes en Python

ABR vs DFS

ABR

  • Cible proche du sommet de départ
  • Applications :
    • Exploration du Web
    • Trouver plus court chemin dans graphes non pondérés
    • Trouver emplacements connectés avec GPS
    • Utilisé dans autres algorithmes plus complexes

DFS

  • Loin du sommet de départ
  • Applications :
    • Résoudre énigmes avec une seule solution (p. ex. labyrinthes)
    • Détection cycles dans graphes
    • Trouver plus court chemin dans graphe pondéré
    • Utilisé dans autres algorithmes plus complexes
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...