Depth-First Search (DFS)

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Baum-/Graph-Traversierung

• Prozess, bei dem alle Knoten besucht werden
• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Tiefensuche – Binärbäume

• Inorder
• Preorder
• Postorder

Inorder-Traversierung

• Reihenfolge: Links

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung

• Reihenfolge: Links -> Aktuell -> Rechts

Inorder-Traversierung – Implementierung

• Reihenfolge: Links -> Aktuell -> 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

• Komplexität: $O(n)$
  • $n$ -> Anzahl der Knoten

Preorder-Traversierung

• Reihenfolge: Aktuell

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung

• Reihenfolge: Aktuell -> Links -> Rechts

Preorder-Traversierung – Implementierung

• Reihenfolge: Wurzel -> 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

• Komplexität: $O(n)$
  • $n$ -> Anzahl der Knoten

Postorder

• Reihenfolge: Links

Postorder

• Reihenfolge: Links -> Rechts

Postorder

• Reihenfolge: Links -> Rechts -> Aktuell

• Komplexität: $O(n)$

  • $n$ -> Anzahl der Knoten

Wann Inorder, Preorder und Postorder nutzen

• Inorder

  • mit BST Werte in aufsteigender Reihenfolge erhalten

• Preorder

  • Kopien eines Baums erstellen
  • Präfixausdrücke erhalten

• Postorder

  • Binärbäume löschen
  • Postfixausdrücke erhalten

Tiefensuche – Graphen

• Graphen können Zyklen haben
  • besuchte Knoten müssen nachgehalten werden
• Schritte:
  1. Bei einem beliebigen Knoten starten
  2. Aktuellen Knoten zur Besuchten-Liste hinzufügen
  3. Für jeden Nachbarn des aktuellen Knotens
     • Falls schon besucht -> überspringen
     • Falls nicht besucht -> rekursiv DFS ausführen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Graphen

Tiefensuche – Implementierung

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)

• Komplexität: $O(V+E)$
  • $V$ -> Anzahl der Knoten
  • $E$ -> Anzahl der Kanten

Lass uns üben!

Datenstrukturen und Algorithmen in Python