Przeszukiwanie w głąb (DFS)

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Przechodzenie po drzewie/grafie

• Proces odwiedzania wszystkich węzłów
• Przeszukiwanie w głąb (DFS)
• Przeszukiwanie wszerz (BFS)

DFS – drzewa binarne

• Inorder
• Preorder
• Postorder

Przechodzenie inorder

• Kolejność: Lewy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder

• Kolejność: Lewy -> Bieżący -> Prawy

Przechodzenie inorder – implementacja

• Kolejność: Lewy -> Bieżący -> Prawy

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

• Złożoność: $O(n)$
  • $n$ -> liczba węzłów

Przechodzenie preorder

• Kolejność: Bieżący

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder

• Kolejność: Bieżący -> Lewy -> Prawy

Przechodzenie preorder – implementacja

• Kolejność: Korzeń -> Lewy -> Prawy

  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

• Złożoność: $O(n)$
  • $n$ -> liczba węzłów

Przechodzenie postorder

• Kolejność: Lewy

Przechodzenie postorder

• Kolejność: Lewy -> Prawy

Przechodzenie postorder

• Kolejność: Lewy -> Prawy -> Bieżący

• Złożoność: $O(n)$

  • $n$ -> liczba węzłów

Kiedy używać inorder, preorder i postorder

• inorder

  • odczyt wartości węzłów BST w porządku rosnącym

• preorder

  • tworzenie kopii drzewa
  • uzyskiwanie wyrażeń prefiksowych

• postorder

  • usuwanie drzew binarnych
  • uzyskiwanie wyrażeń postfiksowych

Przeszukiwanie w głąb – grafy

• Grafy mogą zawierać cykle
  • konieczne śledzenie odwiedzonych wierzchołków
• Kroki:
  1. Rozpocznij od dowolnego wierzchołka
  2. Dodaj bieżący wierzchołek do listy odwiedzonych
  3. Dla każdego sąsiedniego wierzchołka bieżącego węzła
     • Jeśli był odwiedzony -> zignoruj go
     • Jeśli nie był odwiedzony -> wykonaj DFS rekurencyjnie

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – grafy

Przeszukiwanie w głąb – implementacja

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)

• Złożoność: $O(V+E)$
  • $V$ -> liczba wierzchołków
  • $E$ -> liczba krawędzi

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie