Bäume und Graphen

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Bäume – Definition

Ein Bild eines Baums mit Knoten.

  • Knotenbasierte Datenstrukturen
  • Jeder Knoten kann Verbindungen zu mehr als einem Knoten haben.
Datenstrukturen und Algorithmen in Python

Bäume – Grundbegriffe

Ein Bild eines Baums mit Knoten. Der Wurzelknoten ist gelb markiert.

Datenstrukturen und Algorithmen in Python

Bäume – Grundbegriffe

Ein Bild eines Baums mit Knoten. Der Wurzelknoten ist gelb markiert. Ein Elternknoten ist orange markiert.

Datenstrukturen und Algorithmen in Python

Bäume – Grundbegriffe

Ein Bild eines Baums mit Knoten. Der Wurzelknoten ist gelb markiert. Ein Elternknoten ist orange und seine Kinder sind grün.

Datenstrukturen und Algorithmen in Python

Bäume – Grundbegriffe

Ein Bild eines Baums mit Knoten.

Datenstrukturen und Algorithmen in Python

Bäume – Grundbegriffe

Ein Bild eines Baums mit Knoten und seinen Ebenen.

Datenstrukturen und Algorithmen in Python

Bäume – Binärbaum

Grafische Darstellung eines Binärbaums.

  • Jeder Knoten hat:
    • keine Kinder
    • ein Kind
    • zwei Kinder
Datenstrukturen und Algorithmen in Python

Bäume – Binärbaum-Implementierung

class TreeNode:

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

Ein Bild eines Baums mit Knoten.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Datenstrukturen und Algorithmen in Python

Bäume – reale Anwendungen

  • Speichern hierarchischer Beziehungen
    • Dateisystem eines Computers
    • Struktur eines HTML-Dokuments

  • Schach: mögliche Züge des Gegners

  • Such- und Sortieralgorithmen

Datenstrukturen und Algorithmen in Python

Graphen

Ein Bild eines Graphen mit Knoten.

  • Menge aus:
    • Knoten/Vertices
    • Kanten/Edges
  • Bäume sind eine Art Graph
Datenstrukturen und Algorithmen in Python

Graphen – Typen

  • Gerichtete Graphen:
    • Spezielle Richtung

Bild eines gerichteten Graphen.

Datenstrukturen und Algorithmen in Python

Graphen – Typen

  • Ungerichtete Graphen:
    • Kanten haben keine Richtung
    • Beziehung ist wechselseitig

Bild eines ungerichteten Graphen.

Datenstrukturen und Algorithmen in Python

Graphen – Typen

  • Gewichtete Graphen:
    • numerische Werte an den Kanten
    • können gerichtet oder ungerichtet sein

Ein Bild eines ungerichteten Graphen mit Städtenamen und Entfernungen.

Datenstrukturen und Algorithmen in Python

Graphen vs. Bäume

Bäume

  • Dürfen keine Zyklen haben
  • Alle Knoten müssen verbunden sein

Ein Bild eines Baums mit Knoten.

Graphen

  • Können Zyklen haben
  • Es kann unverbundene Knoten geben

Ein Bild eines Graphen mit Knoten.

Datenstrukturen und Algorithmen in Python

Graphen vs. Bäume

Bäume

  • Dürfen keine Zyklen haben
  • Alle Knoten müssen verbunden sein

Ein Bild eines Baums mit Knoten.

Graphen

  • Können Zyklen haben
  • Es kann unverbundene Knoten geben

Ein Bild eines Graphen mit Knoten. Ein Knoten ist nicht mit dem Rest verbunden.

Datenstrukturen und Algorithmen in Python

Graphen – Praxisbeispiele

  • Nutzerbeziehungen in sozialen Netzwerken
    • Freundschaft
    • folgt
    • Likes
    • usw.
  • Orte und Entfernungen
    • Routen optimieren
  • Graph-Datenbanken
  • Such- und Sortieralgorithmen
Datenstrukturen und Algorithmen in Python

Graphen – Implementierung

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)

Bild eines gerichteten Graphen.

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' : []
}
Datenstrukturen und Algorithmen in Python

Lass uns üben!

Datenstrukturen und Algorithmen in Python

Preparing Video For Download...