Arbori și grafuri

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Arbori - definiție

Imagine a unui arbore cu noduri.

  • Structuri de date bazate pe noduri
  • Fiecare nod poate avea legături către mai multe noduri.
Structuri de date și algoritmi în Python

Arbori - terminologie

Imagine a unui arbore cu noduri. Nodul rădăcină este colorat cu galben.

Structuri de date și algoritmi în Python

Arbori - terminologie

Imagine a unui arbore cu noduri. Nodul rădăcină este colorat cu galben. Un nod părinte este colorat cu portocaliu.

Structuri de date și algoritmi în Python

Arbori - terminologie

Imagine a unui arbore cu noduri. Nodul rădăcină este colorat cu galben. Un nod părinte este colorat cu portocaliu, iar copiii săi sunt colorați cu verde.

Structuri de date și algoritmi în Python

Arbori - terminologie

Imagine a unui arbore cu noduri.

Structuri de date și algoritmi în Python

Arbori - terminologie

Imagine a unui arbore cu noduri și nivelurile sale.

Structuri de date și algoritmi în Python

Arbori - arbore binar

Reprezentare grafică a unui arbore binar.

  • Fiecare nod are:
    • zero copii
    • un copil
    • doi copii
Structuri de date și algoritmi în Python

Arbori - implementare arbore binar

class TreeNode:

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

Imagine a unui arbore cu noduri.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Structuri de date și algoritmi în Python

Arbori - utilizări reale

  • Stocarea relațiilor ierarhice
    • Sistemul de fișiere al unui calculator
    • Structura unui document HTML

  • Șah: mutările posibile ale adversarului

  • Algoritmi de căutare și sortare

Structuri de date și algoritmi în Python

Grafuri

Imagine a unui graf cu noduri.

  • Mulțime de:
    • noduri/vârfuri
    • legături/muchii
  • Arborii sunt un tip de graf
Structuri de date și algoritmi în Python

Grafuri - tipuri

  • Grafuri orientate:
    • Direcție specifică

Imagine a unui graf orientat.

Structuri de date și algoritmi în Python

Grafuri - tipuri

  • Grafuri neorientate:
    • Muchiile nu au direcție
    • Relația este reciprocă

Imagine a unui graf neorientat.

Structuri de date și algoritmi în Python

Grafuri - tipuri

  • Grafuri ponderate:
    • valori numerice asociate muchiilor
    • pot fi orientate sau neorientate

Imagine a unui graf neorientat cu nume de orașe și distanțele dintre ele.

Structuri de date și algoritmi în Python

Grafuri vs. arbori

Arbori

  • Nu pot conține cicluri
  • Toate nodurile trebuie să fie conectate

Imagine a unui arbore cu noduri.

Grafuri

  • Pot conține cicluri
  • Pot exista noduri neconectate

Imagine a unui graf cu noduri.

Structuri de date și algoritmi în Python

Grafuri vs. arbori

Arbori

  • Nu pot conține cicluri
  • Toate nodurile trebuie să fie conectate

Imagine a unui arbore cu noduri.

Grafuri

  • Pot conține cicluri
  • Pot exista noduri neconectate

Imagine a unui graf cu noduri. Există un nod neconectat cu restul.

Structuri de date și algoritmi în Python

Grafuri - cazuri de utilizare reale

  • Relații între utilizatori în rețele sociale
    • prietenie
    • urmărire
    • apreciere
    • etc.
  • Locații și distanțe
    • optimizarea rutelor
  • Baze de date grafice
  • Algoritmi de căutare și sortare
Structuri de date și algoritmi în Python

Grafuri - implementare

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)

Imagine a unui graf orientat.

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' : []
}
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...