Penelusuran Mendalam (DFS)

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Penelusuran pohon/graf

• Proses mengunjungi semua simpul
• Depth first search (DFS)
• Breadth first search (BFS)

Penelusuran mendalam - pohon biner

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

Penelusuran in-order

• Urutan: Kiri

Penelusuran in-order

• Urutan: Kiri -> Saat ini

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order

• Urutan: Kiri -> Saat ini -> Kanan

Penelusuran in-order - implementasi

• Urutan: Kiri -> Saat ini -> Kanan

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

• Kompleksitas: $O(n)$
  • $n$ -> jumlah simpul

Penelusuran pre-order

• Urutan: Saat ini

Penelusuran pre-order

• Urutan: Saat ini -> Kiri

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order

• Urutan: Saat ini -> Kiri -> Kanan

Penelusuran pre-order - implementasi

• Urutan: Akar -> Kiri -> Kanan

  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

• Kompleksitas: $O(n)$
  • $n$ -> jumlah simpul

Post-order

• Urutan: Kiri

Post-order

• Urutan: Kiri -> Kanan

Post-order

• Urutan: Kiri -> Kanan -> Saat ini

• Kompleksitas: $O(n)$

  • $n$ -> jumlah simpul

Kapan menggunakan in-order, pre-order, dan post-order

• in-order

  • gunakan BST untuk memperoleh nilai simpul naik

• pre-order

  • membuat salinan pohon
  • mendapatkan ekspresi prefiks

• post-order

  • menghapus pohon biner
  • mendapatkan ekspresi postfiks

Penelusuran mendalam - graf

• Graf dapat memiliki siklus
  • perlu melacak simpul yang sudah dikunjungi
• Langkah:
  1. Mulai dari simpul mana pun
  2. Tambahkan simpul saat ini ke daftar terkunjungi
  3. Untuk setiap simpul bertetangga dari simpul saat ini
     • Jika sudah dikunjungi -> abaikan
     • Jika belum -> lakukan DFS secara rekursif

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - graf

Penelusuran mendalam - implementasi

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)

• Kompleksitas: $O(V+E)$
  • $V$ -> jumlah simpul
  • $E$ -> jumlah sisi

Ayo berlatih!

Struktur Data dan Algoritma di Python