Drzewa i grafy

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Drzewa – definicja

Rysunek drzewa z węzłami.

Struktury danych oparte na węzłach
Każdy węzeł może mieć łącza do więcej niż jednego węzła.

Drzewa – terminologia

Rysunek drzewa z węzłami. Węzeł główny jest zaznaczony na żółto.

Drzewa – terminologia

Rysunek drzewa z węzłami. Węzeł główny jest zaznaczony na żółto, węzeł nadrzędny na pomarańczowo.

Drzewa – terminologia

Rysunek drzewa z węzłami. Węzeł główny jest zaznaczony na żółto, węzeł nadrzędny na pomarańczowo, a jego dzieci na zielono.

Drzewa – terminologia

Rysunek drzewa z węzłami.

Drzewa – terminologia

Rysunek drzewa z węzłami i zaznaczonymi poziomami.

Drzewa – drzewo binarne

Graficzna reprezentacja drzewa binarnego.

Każdy węzeł ma:
- zero dzieci
- jedno dziecko
- dwoje dzieci

Drzewa – implementacja drzewa binarnego

class TreeNode:

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

Rysunek drzewa z węzłami.

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

Drzewa – zastosowania

Przechowywanie relacji hierarchicznych
- System plików komputera
- Struktura dokumentu HTML
Szachy: możliwe ruchy przeciwnika
Algorytmy wyszukiwania i sortowania

Grafy

Rysunek grafu z węzłami.

Zbiór:
- węzłów/wierzchołków
- łączy/krawędzi
Drzewa są rodzajem grafu

Grafy – rodzaje

Grafy skierowane:
- Określony kierunek

Rysunek grafu skierowanego.

Grafy – rodzaje

Grafy nieskierowane:
- Krawędzie bez kierunku
- Relacja jest wzajemna

Rysunek grafu nieskierowanego.

Grafy – rodzaje

Grafy ważone:
- wartości liczbowe przypisane krawędziom
- mogą być skierowane lub nieskierowane

Rysunek nieskierowanego grafu z nazwami miast i odległościami między nimi.

Grafy a drzewa

Drzewa

Nie mogą mieć cykli
Wszystkie węzły muszą być połączone

Rysunek drzewa z węzłami.

Grafy

Mogą mieć cykle
Mogą istnieć niepołączone węzły

Rysunek grafu z węzłami.

Grafy a drzewa

Drzewa

Nie mogą mieć cykli
Wszystkie węzły muszą być połączone

Rysunek drzewa z węzłami.

Grafy

Mogą mieć cykle
Mogą istnieć niepołączone węzły

Rysunek grafu z węzłami. Jeden węzeł nie jest połączony z pozostałymi.

Grafy – zastosowania w praktyce

Relacje użytkowników w sieciach społecznościowych
- znajomość
- obserwowanie
- polubienia
- itd.
Lokalizacje i odległości
- optymalizacja tras
Bazy danych grafowych
Algorytmy wyszukiwania i sortowania

Grafy – implementacja

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)

Rysunek grafu skierowanego.

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' : []
}

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie