Derinlik Öncelikli Arama (DFS)

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Ağaç/graf dolaşımı

• Tüm düğümleri ziyaret etme süreci
• Derinlik öncelikli arama (DFS)
• Genişlik öncelikli arama (BFS)

Derinlik öncelikli arama - ikili ağaçlar

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

Sıralı (in-order) dolaşım

• Sıra: Sol

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım

• Sıra: Sol -> Mevcut -> Sağ

Sıralı (in-order) dolaşım - uygulama

• Sıra: Sol -> Mevcut -> Sağ

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

• Karmaşıklık: $O(n)$
  • $n$ -> düğüm sayısı

Öncel (pre-order) dolaşım

• Sıra: Mevcut

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım

• Sıra: Mevcut -> Sol -> Sağ

Öncel (pre-order) dolaşım - uygulama

• Sıra: Kök -> Sol -> Sağ

  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

• Karmaşıklık: $O(n)$
  • $n$ -> düğüm sayısı

Sonral (post-order)

• Sıra: Sol

Sonral (post-order)

• Sıra: Sol -> Sağ

Sonral (post-order)

• Sıra: Sol -> Sağ -> Mevcut

• Karmaşıklık: $O(n)$

  • $n$ -> düğüm sayısı

In-order, pre-order ve post-order ne zaman kullanılır

• in-order

  • Düğümleri artan sırada almak için BST kullanılır

• pre-order

  • ağacın kopyalarını oluşturma
  • önek (prefix) ifadeleri elde etme

• post-order

  • ikili ağaçları silme
  • sonek (postfix) ifadeleri elde etme

Derinlik öncelikli arama - grafikler

• Grafiklerde döngüler olabilir
  • ziyaret edilen düğümler izlenmelidir
• Adımlar:
  1. Herhangi bir düğümden başlayın
  2. Mevcut düğümü ziyaret edilmişler listesine ekleyin
  3. Mevcut düğümün her komşusu için
     • Ziyaret edildiyse -> yok sayın
     • Ziyaret edilmediyse -> özyinelemeli DFS yapın

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - grafikler

Derinlik öncelikli arama - uygulama

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)

• Karmaşıklık: $O(V+E)$
  • $V$ -> düğüm (tepe) sayısı
  • $E$ -> kenar sayısı

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar