Bomen en grafen

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Bomen - definitie

Een afbeelding van een boom met knopen.

Knoop-gebaseerde datastructuren
Elke knoop kan links hebben naar meer dan één knoop.

Bomen - terminologie

Een afbeelding van een boom met knopen. De wortelknoop is geel.

Bomen - terminologie

Een afbeelding van een boom met knopen. De wortelknoop is geel. Een ouderknoop is oranje.

Bomen - terminologie

Een afbeelding van een boom met knopen. De wortelknoop is geel. Een ouderknoop is oranje en zijn kinderen zijn groen.

Bomen - terminologie

Een afbeelding van een boom met knopen.

Bomen - terminologie

Een afbeelding van een boom met knopen op verschillende niveaus.

Bomen - binaire boom

Grafische weergave van een binaire boom.

Elke knoop heeft:
- geen kinderen
- één kind
- twee kinderen

Bomen - implementatie binaire boom

class TreeNode:

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

Een afbeelding van een boom met knopen.

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

Bomen - toepassingen

Opslaan van hiërarchische relaties
- Bestandssysteem van een computer
- Structuur van een HTML-document
Schaken: mogelijke zetten van de tegenstander
Zoek- en sorteeralgoritmen

Grafen

Een afbeelding van een graaf met knopen.

Verzameling van:
- knopen/vertices
- links/randen
Bomen zijn een soort graaf

Grafen - typen

Gerichte grafen:
- Specifieke richting

Afbeelding van een gerichte graaf.

Grafen - typen

Ongerichte grafen:
- Randen hebben geen richting
- De relatie is wederkerig

Afbeelding van een ongerichte graaf.

Grafen - typen

Gewogen grafen:
- numerieke waarden aan de randen
- kunnen gericht of ongericht zijn

Een afbeelding van een ongerichte graaf met stadsnamen en afstanden.

Grafen vs. bomen

Bomen

Hebben geen cycli
Alle knopen zijn verbonden

Een afbeelding van een boom met knopen.

Grafen

Kunnen cycli hebben
Er kunnen niet-verbonden knopen zijn

Een afbeelding van een graaf met knopen.

Grafen vs. bomen

Bomen

Hebben geen cycli
Alle knopen zijn verbonden

Een afbeelding van een boom met knopen.

Grafen

Kunnen cycli hebben
Er kunnen niet-verbonden knopen zijn

Een afbeelding van een graaf met knopen. Er is een knoop die niet is verbonden met de rest.

Grafen - toepassingen in de echte wereld

Gebruikersrelaties in sociale netwerken
- vriendschap
- volgt
- vindt leuk
- enz.
Locaties en afstanden
- routes optimaliseren
Grafendatabases
Zoek- en sorteeralgoritmen

Grafen - implementatie

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)

Afbeelding van een gerichte graaf.

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

Laten we oefenen!

Datastructuren en algoritmen in Python