Djupet-först-sökning (DFS)

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Traversering av träd/graf

• Processen att besöka alla noder
• Djupet-först-sökning (DFS)
• Bredden-först-sökning (BFS)

Djupet-först-sökning – binära träd

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

In-order-traversering

• Ordning: Vänster

In-order-traversering

• Ordning: Vänster -> Aktuell

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering

• Ordning: Vänster -> Aktuell -> Höger

In-order-traversering – implementation

• Ordning: Vänster -> Aktuell -> Höger

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

• Komplexitet: $O(n)$
  • $n$ -> antal noder

Pre-order-traversering

• Ordning: Aktuell

Pre-order-traversering

• Ordning: Aktuell -> Vänster

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering

• Ordning: Aktuell -> Vänster -> Höger

Pre-order-traversering – implementation

• Ordning: Rot -> Vänster -> Höger

  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

• Komplexitet: $O(n)$
  • $n$ -> antal noder

Post-order

• Ordning: Vänster

Post-order

• Ordning: Vänster -> Höger

Post-order

• Ordning: Vänster -> Höger -> Aktuell

• Komplexitet: $O(n)$

  • $n$ -> antal noder

När används in-order, pre-order och post-order?

• in-order

  • används med BST för att hämta nodvärden i stigande ordning

• pre-order

  • skapa kopior av ett träd
  • hämta prefixuttryck

• post-order

  • ta bort binära träd
  • hämta postfixuttryck

Djupet-först-sökning – grafer

• Grafer kan ha cyklar
  • besökta hörn måste spåras
• Steg:
  1. Börja vid valfritt hörn
  2. Lägg till aktuellt hörn i listan över besökta hörn
  3. För varje grannhörn till aktuell nod
     • Om det är besökt -> ignorera det
     • Om det inte är besökt -> utför DFS rekursivt

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – grafer

Djupet-först-sökning – implementation

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)

• Komplexitet: $O(V+E)$
  • $V$ -> antal hörn
  • $E$ -> antal kanter

Nu kör vi en övning!

Datastrukturer och algoritmer i Python