Ağaçlar ve grafikler

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Ağaçlar - tanım

Düğümleri olan bir ağacın resmi.

Düğüm tabanlı veri yapıları
Her düğümün birden fazla düğüme bağlantısı olabilir.

Ağaçlar - terimler

Düğümleri olan bir ağacın resmi. Kök düğüm sarı renkte.

Ağaçlar - terimler

Düğümleri olan bir ağacın resmi. Kök düğüm sarı, bir ebeveyn düğüm turuncu renkte.

Ağaçlar - terimler

Düğümleri olan bir ağacın resmi. Kök düğüm sarı, bir ebeveyn düğüm turuncu ve onun çocukları yeşil renkte.

Ağaçlar - terimler

Düğümleri olan bir ağacın resmi.

Ağaçlar - terimler

Farklı seviyeleri gösterilen düğümlü bir ağacın resmi.

Ağaçlar - ikili ağaç

İkili ağacın görsel gösterimi.

Her düğümün olabilir:
- sıfır çocuk
- bir çocuk
- iki çocuk

Ağaçlar - ikili ağaç uygulaması

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

Düğümleri olan bir ağacın resmi.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

Ağaçlar - gerçek kullanım alanları

Hiyerarşik ilişkileri saklama
- Bir bilgisayarın dosya sistemi
- Bir HTML belgesinin yapısı
Satranç: rakibin olası hamleleri
Arama ve sıralama algoritmaları

Grafikler

Düğümleri olan bir grafiğin resmi.

Şunların kümesi:
- düğümler/tepe noktaları
- bağlantılar/kenarlar
Ağaçlar bir grafik türüdür

Grafikler - türler

Yönlü grafikler:
- Belirli yön

Yönlü bir grafiğin resmi.

Grafikler - türler

Yönsüz grafikler:
- Kenarların yönü yoktur
- İlişki karşılıklıdır

Yönsüz bir grafiğin resmi.

Grafikler - türler

Ağırlıklı grafikler:
- kenarlarla ilişkili sayısal değerler
- yönlü veya yönsüz olabilir

Bazı şehir adları ve aralarındaki mesafeler bulunan yönsüz bir grafiğin resmi.

Grafikler vs. ağaçlar

Ağaçlar

Döngü içeremez
Tüm düğümler bağlı olmalıdır

Düğümleri olan bir ağacın resmi.

Grafikler

Döngü içerebilir
Bağlı olmayan düğümler olabilir

Düğümleri olan bir grafiğin resmi.

Grafikler vs. ağaçlar

Ağaçlar

Döngü içeremez
Tüm düğümler bağlı olmalıdır

Düğümleri olan bir ağacın resmi.

Grafikler

Döngü içerebilir
Bağlı olmayan düğümler olabilir

Düğümleri olan bir grafiğin resmi. Geri kalanla bağlantısı olmayan bir düğüm var.

Grafikler - gerçek dünya kullanım alanları

Sosyal ağlarda kullanıcı ilişkileri
- arkadaşlık
- takip
- beğeni
- vb.
Konumlar ve mesafeler
- rotaları optimize etme
Graf veritabanları
Arama ve sıralama algoritmaları

Grafikler - uygulama

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Yönlü bir grafiğin resmi.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar