Stromy a grafy

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Stromy – definice

Obrázek stromu s uzly.

Datové struktury založené na uzlech
Každý uzel může mít vazby na více než jeden uzel.

Stromy – terminologie

Obrázek stromu s uzly. Kořenový uzel je žlutý.

Stromy – terminologie

Obrázek stromu s uzly. Kořenový uzel je žlutý. Rodičovský uzel je oranžový.

Stromy – terminologie

Obrázek stromu s uzly. Kořenový uzel je žlutý. Rodičovský uzel je oranžový a jeho potomci jsou zelení.

Stromy – terminologie

Obrázek stromu s uzly.

Stromy – terminologie

Obrázek stromu s uzly a jeho různými úrovněmi.

Stromy – binární strom

Grafické znázornění binárního stromu.

Každý uzel má:
- žádné potomky
- jednoho potomka
- dva potomky

Stromy – implementace binárního stromu

class TreeNode:

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

Obrázek stromu s uzly.

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

Stromy – praktické využití

Ukládání hierarchických vztahů
- Souborový systém počítače
- Struktura HTML dokumentu
Šachy: možné tahy soupeře
Algoritmy vyhledávání a řazení

Grafy

Obrázek grafu s uzly.

Množina:
- uzlů/vrcholů
- vazeb/hran
Stromy jsou typem grafu

Grafy – typy

Orientované grafy:
- Určený směr

Obrázek orientovaného grafu.

Grafy – typy

Neorientované grafy:
- Hrany nemají směr
- Vztah je oboustranný

Obrázek neorientovaného grafu.

Grafy – typy

Ohodnocené grafy:
- číselné hodnoty přiřazené hranám
- mohou být orientované i neorientované

Obrázek neorientovaného grafu s názvy měst a vzdálenostmi mezi nimi.

Grafy vs. stromy

Stromy

Nemohou obsahovat cykly
Všechny uzly musí být propojeny

Obrázek stromu s uzly.

Grafy

Mohou obsahovat cykly
Mohou existovat nepropojené uzly

Obrázek grafu s uzly.

Grafy vs. stromy

Stromy

Nemohou obsahovat cykly
Všechny uzly musí být propojeny

Obrázek stromu s uzly.

Grafy

Mohou obsahovat cykly
Mohou existovat nepropojené uzly

Obrázek grafu s uzly. Jeden uzel není propojen se zbytkem.

Grafy – využití v praxi

Vztahy uživatelů v sociálních sítích
- přátelství
- sledování
- lajky
- atd.
Místa a vzdálenosti
- optimalizace tras
Grafové databáze
Algoritmy vyhledávání a řazení

Grafy – implementace

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)

Obrázek orientovaného grafu.

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

Pojďme procvičovat!

Datové struktury a algoritmy v Pythonu