Pohon dan graf

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Pohon - definisi

Gambar pohon dengan node.

  • Struktur data berbasis node
  • Tiap node dapat punya tautan ke lebih dari satu node.
Struktur Data dan Algoritma di Python

Pohon - terminologi

Gambar pohon dengan node. Node akar berwarna kuning.

Struktur Data dan Algoritma di Python

Pohon - terminologi

Gambar pohon dengan node. Node akar berwarna kuning. Sebuah node induk berwarna oranye.

Struktur Data dan Algoritma di Python

Pohon - terminologi

Gambar pohon dengan node. Node akar berwarna kuning. Sebuah node induk berwarna oranye dan anaknya berwarna hijau.

Struktur Data dan Algoritma di Python

Pohon - terminologi

Gambar pohon dengan node.

Struktur Data dan Algoritma di Python

Pohon - terminologi

Gambar pohon dengan node pada berbagai level.

Struktur Data dan Algoritma di Python

Pohon - pohon biner

Representasi grafis pohon biner.

  • Setiap node memiliki:
    • nol anak
    • satu anak
    • dua anak
Struktur Data dan Algoritma di Python

Pohon - implementasi pohon biner

class TreeNode:

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

Gambar pohon dengan node.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Struktur Data dan Algoritma di Python

Pohon - kegunaan nyata

  • Menyimpan relasi hierarkis
    • Sistem berkas komputer
    • Struktur dokumen HTML

  • Catur: kemungkinan langkah lawan

  • Algoritma pencarian dan pengurutan

Struktur Data dan Algoritma di Python

Graf

Gambar graf dengan node.

  • Kumpulan:
    • node/vertex
    • tautan/edge
  • Pohon adalah jenis graf
Struktur Data dan Algoritma di Python

Graf - tipe

  • Graf berarah:
    • Arah tertentu

Gambar graf berarah.

Struktur Data dan Algoritma di Python

Graf - tipe

  • Graf tak berarah:
    • Edge tidak punya arah
    • Relasi bersifat saling

Gambar graf tak berarah.

Struktur Data dan Algoritma di Python

Graf - tipe

  • Graf berbobot:
    • nilai numerik pada edge
    • bisa berarah atau tak berarah

Gambar graf tak berarah dengan nama kota dan jaraknya.

Struktur Data dan Algoritma di Python

Graf vs. pohon

Pohon

  • Tidak boleh punya siklus
  • Semua node harus terhubung

Gambar pohon dengan node.

Graf

  • Boleh punya siklus
  • Bisa ada node yang tak terhubung

Gambar graf dengan node.

Struktur Data dan Algoritma di Python

Graf vs. pohon

Pohon

  • Tidak boleh punya siklus
  • Semua node harus terhubung

Gambar pohon dengan node.

Graf

  • Boleh punya siklus
  • Bisa ada node yang tak terhubung

Gambar graf dengan node. Ada satu node yang tidak terhubung dengan yang lain.

Struktur Data dan Algoritma di Python

Graf - kasus penggunaan nyata

  • Relasi pengguna di media sosial
    • pertemanan
    • mengikuti
    • menyukai
    • dll.
  • Lokasi dan jarak
    • optimasi rute
  • Basis data graf
  • Algoritma pencarian dan pengurutan
Struktur Data dan Algoritma di Python

Graf - implementasi

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)

Gambar graf berarah.

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' : []
}
Struktur Data dan Algoritma di Python

Ayo berlatih!

Struktur Data dan Algoritma di Python

Preparing Video For Download...