Prohledávání do hloubky (DFS)

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Procházení stromů/grafů

• Proces procházení všech uzlů
• Prohledávání do hloubky (DFS)
• Prohledávání do šířky (BFS)

DFS – binární stromy

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

Průchod in-order

• Pořadí: Levý

Průchod in-order

• Pořadí: Levý -> Aktuální

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order

• Pořadí: Levý -> Aktuální -> Pravý

Průchod in-order – implementace

• Pořadí: Levý -> Aktuální -> Pravý

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

• Složitost: $O(n)$
  • $n$ -> počet uzlů

Průchod pre-order

• Pořadí: Aktuální

Průchod pre-order

• Pořadí: Aktuální -> Levý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order

• Pořadí: Aktuální -> Levý -> Pravý

Průchod pre-order – implementace

• Pořadí: Kořen -> Levý -> Pravý

  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

• Složitost: $O(n)$
  • $n$ -> počet uzlů

Post-order

• Pořadí: Levý

Post-order

• Pořadí: Levý -> Pravý

Post-order

• Pořadí: Levý -> Pravý -> Aktuální

• Složitost: $O(n)$

  • $n$ -> počet uzlů

Kdy použít in-order, pre-order a post-order

• in-order

  • BST pro získání hodnot uzlů ve vzestupném pořadí

• pre-order

  • vytváření kopií stromu
  • získání prefixových výrazů

• post-order

  • mazání binárních stromů
  • získání postfixových výrazů

Prohledávání do hloubky – grafy

• Grafy mohou obsahovat cykly
  • je nutné sledovat navštívené vrcholy
• Postup:
  1. Začít v libovolném vrcholu
  2. Přidat aktuální vrchol do seznamu navštívených
  3. Pro každý sousední vrchol aktuálního uzlu
     • Pokud byl navštíven -> ignorovat
     • Pokud nebyl navštíven -> rekurzivně provést DFS

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – grafy

Prohledávání do hloubky – implementace

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)

• Složitost: $O(V+E)$
  • $V$ -> počet vrcholů
  • $E$ -> počet hran

Lass uns üben!

Datové struktury a algoritmy v Pythonu