Graphen

Graphen bestehen aus Knoten und Kanten. Kanten verbinden jeweils zwei Knoten. Kanten können gerichtet sein (d.h. sie können nur in einer Richtung durchlaufen werden, ähnlich wie eine Einbahnstraße) oder ungerichtet und sie können Gewichte besitzen (z.B. Länge einer Strecke). Die Gewichte werden an den Kanten notiert. Graphen, deren Kanten keine Gewichte besitzen, heißen ungewichtet (auch: unbewertet).

Folgen von Kanten, die zwei Knoten verbinden heißen Pfad. Ein Pfad, dessen Anfangs- und Endknoten übereinstimmt heißt geschlossener Pfad. Ein Knoten A heißt von einem anderen Knoten B aus erreichbar, wenn es von B nach A einen Pfad gibt. Ein geschlossener Pfad, der keine Kante zweimal enthält, heißt Zyklus. Ein Graph, der mindestens einen Zyklus besitzt, heißt zyklisch.

Ein ungerichteter Graph heißt zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert.

Ein gerichteter Graph heißt

stark zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert
(damit ist natürlich insbesondere gemeint, dass die Kanten in der vorgegebenen Richtung durchlaufen werden),
schwach zusammenhängend, wenn er als ungerichteter Graph zusammenhängend wäre und
ansonsten unzusammenhängend (auch bei ungerichteten Graphen).

Beispiel 1

Dieser Graph ist gewichtet (die Kantengewichte geben die Straßen-Distanz in Kilometern an), ungerichtet, zyklisch und nicht zusammenhängend.

Knoten wie Helgoland in Beispiel 3, die zu keinem anderen Knoten eine Kante besitzen, heißen isoliert.

Aufgabe 1

Beschreibe die folgenden Graphen mit möglichst vielen der obigen Fachwörter.

a)	b)	c)	d)	e)

Lösung

Aufgabe 2

Derselbe Graph kann auf unterschiedliche Weise als Diagramm dargestellt werden. Welche der Diagramme im Bild rechts stellen denselben Graph dar?

Lösung

Aufgabe 3

Nennen Sie je zwei Anwendungsbeispiele, die als gerichtete, ungerichtete oder gewichtete Graphen dargestellt werden können.

Tiefensuche (für interessierte Schüler/innen)

Die Behandlung der Tiefensuche ist im Lehrplan leider nicht vorgesehen. Weil dieser Algorithmus sich sehr gut eignet, um einen Einblick in die Programmierung mithilfe von rekursiven Methodenaufrufen zu bekommen, finden interessierte Schüler/innen hier eine Einführung zum Selbststudium. Falls Sie Fragen dazu haben, stehe ich gerne zur Verfügung!

Warteschlange (Queue)

Für die Breitensuche brauchen wir eine neue Datenstruktur, die Warteschlange (engl.: Queue). In einer Warteschlange können beliebig viele Elemente nacheinander abgelegt werden. Sie besitzt eine Methode addLast um Elemente am hinteren Ende der Warteschlange anzufügen und eine Methode removeFirst um Elemente am vorderen Ende zu entnehmen.

In der Programmiersprache Java gibt es mehrere Klassen, die die Aufgaben einer Warteschlange erfüllen können, daher sind die Methoden der Warteschlange im Interface Queue definiert, das von mehreren Klassen implementiert wird, insbesondere von der Klasse LinkedList<T>, die wir im Folgenden verwenden. Dabei ist T die Klasse der Objekte, die in der LinkedList gespeichert werden können. Wollen wir beispielsweise Zeichenketten in der LinkedList speichern, so gehen wir folgendermaßen vor: