Ein Graf ist in der Mathematik und Informatik eine Struktur, die aus einer Menge von Knoten (auch als Punkte oder Vertices bezeichnet) und einer Menge von Kanten (Edges) besteht, die die Knoten miteinander verbinden. Grafen können gerichtet oder ungerichtet sein, je nachdem, ob die Kanten eine Richtung haben oder nicht. Sie werden häufig verwendet, um Beziehungen zwischen Objekten darzustellen, wie zum Beispiel in sozialen Netzwerken, Verkehrsnetzwerken oder in der Computerwissenschaft zur Modellierung von Datenstrukturen. Grafen können auch gewichtet sein, was bedeutet, dass den Kanten Werte zugewiesen werden, die beispielsweise Entfernungen oder Kosten darstellen.