Ein Graph G ist eine Menge von Knoten V (engl. vertices) und Kanten E (engl. edges).
Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.
Ein Graph heißt zusammenhängend, wenn es zwischen den Knoten einen Weg gibt.
Von gerichteten Graphen sprechen wir, wenn die Kanten mit Pfeilen versehen werden. Dann kann die Kante nur in Richtung des Pfeils beschritten werden.
Wofür braucht man Graphen?
Man kann z.B. ein Computernetzwerk oder eine Straßenkarte als Graph darstellen.
Wenn man dann zusätzlich die Katen mit sogenannten Gewichten versieht (z.B. die Netzwerkgeschwindigkeit oder die Länge der Straße), kann man den besten Weg von A nach B berechnen.