Búsqueda en profundidad (DFS)

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Recorrido de árboles/grafos

• Proceso de visitar todos los nodos
• Búsqueda en profundidad (DFS)
• Búsqueda en anchura (BFS)

Búsqueda en profundidad - árboles binarios

• In-order
• Pre-order
• Post-order

Recorrido in-order

• Orden: Izquierda

Recorrido in-order

• Orden: Izquierda -> Actual

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order

• Orden: Izquierda -> Actual -> Derecha

Recorrido in-order - implementación

• Orden: Izquierda -> Actual -> Derecha

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

• Complejidad: $O(n)$
  • $n$ -> número de nodos

Recorrido pre-order

• Orden: Actual

Recorrido pre-order

• Orden: Actual -> Izquierda

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order

• Orden: Actual -> Izquierda -> Derecha

Recorrido pre-order - implementación

• Orden: Raíz -> Izquierda -> Derecha

  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

• Complejidad: $O(n)$
  • $n$ -> número de nodos

Post-order

• Orden: Izquierda

Post-order

• Orden: Izquierda -> Derecha

Post-order

• Orden: Izquierda -> Derecha -> Actual

• Complejidad: $O(n)$

  • $n$ -> número de nodos

Cuándo usar in-order, pre-order y post-order

• in-order

  • usar BST para obtener valores en orden ascendente

• pre-order

  • crear copias de un árbol
  • obtener expresiones prefijas

• post-order

  • borrar árboles binarios
  • obtener expresiones posfijas

Búsqueda en profundidad - grafos

• Los grafos pueden tener ciclos
  • hay que registrar los vértices visitados
• Pasos:
  1. Empieza en cualquier vértice
  2. Añade el vértice actual a la lista de visitados
  3. Para cada vértice adyacente del actual
     • Si ya se visitó -> ignóralo
     • Si no se visitó -> haz DFS recursivo

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - grafos

Búsqueda en profundidad - implementación

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)

• Complejidad: $O(V+E)$
  • $V$ -> número de vértices
  • $E$ -> número de aristas

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python