Busca em Profundidade (DFS)

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Percurso em árvore/grafo

• Processo de visitar todos os nós
• Depth First Search (DFS)
• Breadth First Search (BFS)

Busca em profundidade - árvores binárias

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

Travessia in-order

• Ordem: Esquerda

Travessia in-order

• Ordem: Esquerda -> Atual

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order

• Ordem: Esquerda -> Atual -> Direita

Travessia in-order - implementação

• Ordem: Esquerda -> Atual -> Direita

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

• Complexidade: $O(n)$
  • $n$ -> número de nós

Travessia pre-order

• Ordem: Atual

Travessia pre-order

• Ordem: Atual -> Esquerda

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order

• Ordem: Atual -> Esquerda -> Direita

Travessia pre-order - implementação

• Ordem: Raiz -> Esquerda -> Direita

  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

• Complexidade: $O(n)$
  • $n$ -> número de nós

Post-order

• Ordem: Esquerda

Post-order

• Ordem: Esquerda -> Direita

Post-order

• Ordem: Esquerda -> Direita -> Atual

• Complexidade: $O(n)$

  • $n$ -> número de nós

Quando usar in-order, pre-order e post-order

• in-order

  • usar ABB para obter valores em ordem crescente

• pre-order

  • copiar uma árvore
  • obter expressões prefixas

• post-order

  • deletar árvores binárias
  • obter expressões posfixas

Busca em profundidade - grafos

• Grafos podem ter ciclos
  • é preciso registrar os vértices visitados
• Passos:
  1. Comece em qualquer vértice
  2. Adicione o vértice atual à lista de visitados
  3. Para cada vértice adjacente do atual
     • Se já foi visitado -> ignore
     • Se não foi -> faça DFS recursivamente

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - grafos

Busca em profundidade - implementação

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)

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

Vamos praticar!

Estruturas de Dados e Algoritmos em Python