Căutarea în adâncime (DFS)

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Parcurgerea arborilor/grafurilor

• Procesul de vizitare a tuturor nodurilor
• Căutare în adâncime (DFS)
• Căutare în lățime (BFS)

Căutare în adâncime - arbori binari

• În ordine
• Pre-ordine
• Post-ordine

Parcurgere în ordine

• Ordine: Stânga

Parcurgere în ordine

• Ordine: Stânga -> Curent

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine

• Ordine: Stânga -> Curent -> Dreapta

Parcurgere în ordine - implementare

• Ordine: Stânga -> Curent -> Dreapta

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

• Complexitate: $O(n)$
  • $n$ -> numărul de noduri

Parcurgere în pre-ordine

• Ordine: Curent

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine

• Ordine: Curent -> Stânga -> Dreapta

Parcurgere în pre-ordine - implementare

• Ordine: Rădăcină -> Stânga -> Dreapta

  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

• Complexitate: $O(n)$
  • $n$ -> numărul de noduri

Post-ordine

• Ordine: Stânga

Post-ordine

• Ordine: Stânga -> Dreapta

Post-ordine

• Ordine: Stânga -> Dreapta -> Curent

• Complexitate: $O(n)$

  • $n$ -> numărul de noduri

Când să folosiți în ordine, pre-ordine și post-ordine

• în ordine

  • folosit în BST pentru a obține valorile nodurilor în ordine crescătoare

• pre-ordine

  • copierea unui arbore
  • obținerea expresiilor prefix

• post-ordine

  • ștergerea arborilor binari
  • obținerea expresiilor postfix

Căutare în adâncime - grafuri

• Grafurile pot conține cicluri
  • este necesar să urmăriți vârfurile vizitate
• Pași:
  1. Începeți de la orice vârf
  2. Adăugați vârful curent în lista vizitate
  3. Pentru fiecare vârf adiacent nodului curent
     • Dacă a fost vizitat -> ignorați-l
     • Dacă nu a fost vizitat -> aplicați DFS recursiv

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - grafuri

Căutare în adâncime - implementare

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)

• Complexitate: $O(V+E)$
  • $V$ -> numărul de vârfuri
  • $E$ -> numărul de muchii

Să exersăm!

Structuri de date și algoritmi în Python