Depth-first search (DFS)

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Boom-/graaftraversal

• Proces om alle knopen te bezoeken
• Depth-first search (DFS)
• Breadth-first search (BFS)

Depth-first search - binaire bomen

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

In-order traverseren

• Ordening: Links

In-order traverseren

• Ordening: Links -> Huidig

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren

• Ordening: Links -> Huidig -> Rechts

In-order traverseren - implementatie

• Ordening: Links -> Huidig -> Rechts

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

• Complexiteit: $O(n)$
  • $n$ -> aantal knopen

Pre-order traverseren

• Ordening: Huidig

Pre-order traverseren

• Ordening: Huidig -> Links

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren

• Ordening: Huidig -> Links -> Rechts

Pre-order traverseren - implementatie

• Ordening: Wortel -> Links -> Rechts

  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

• Complexiteit: $O(n)$
  • $n$ -> aantal knopen

Post-order

• Ordening: Links

Post-order

• Ordening: Links -> Rechts

Post-order

• Ordening: Links -> Rechts -> Huidig

• Complexiteit: $O(n)$

  • $n$ -> aantal knopen

Wanneer in-order, pre-order en post-order gebruiken

• in-order

  • gebruik BST om knoopwaarden oplopend te krijgen

• pre-order

  • kopieën van een boom maken
  • prefix-expressies krijgen

• post-order

  • binaire bomen verwijderen
  • postfix-expressies krijgen

Depth-first search - grafen

• Grafen kunnen cycli hebben
  • houd bezochte knopen bij
• Stappen:
  1. Start bij een willekeurige knoop
  2. Voeg huidige knoop toe aan bezochte lijst
  3. Voor elke aangrenzende knoop van de huidige
     • Als al bezocht -> negeren
     • Zo niet -> voer recursief DFS uit

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - grafen

Depth-first search - implementatie

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)

• Complexiteit: $O(V+E)$
  • $V$ -> aantal knopen
  • $E$ -> aantal verbindingen

Laten we oefenen!

Datastructuren en algoritmen in Python