Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Graphen

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.

Adjazenzmatrix

Die oben verwendete graphische Darstellung ist zwar anschaulich, für algorithmische Verarbeitung aber häufig eher ungünstig. Eine andere Darstellung von Graphen ist ihre Adjazenzmatrix (man nennt zwei Knoten, die durch eine Kante verbunden sind, auch adjazent). Dabei wird eine Art Tabelle aufgestellt, deren Spalten- und Zeilenanzahl der Anzahl der Knoten entspricht (die im Folgenden verwendeten Zeilen- und Spaltenbeschriftungen sind nicht Teil der Adjazenzmatrix und dienen nur der Veranschaulichung). Die Adjazenzmatrix enthält dann als Eintrag

0, wenn es keine Kante zwischen dem links stehenden und dem oben stehenden Knoten gibt
1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist
ansonsten das Kantengewicht

Beispiel 2

(Adjazenzmatrix eines gerichteten Graphen)

	Knoten 1	Knoten 3
Knoten 1	0	1
Knoten 2	1	0
Knoten 3	0	0

Beispiel 3

	Knoten 1	Knoten 2	Knoten 3
Knoten 1	0	22	17
Knoten 2	22	0	0
Knoten 3	17	0	0

Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch bzgl. der Diagonale von links oben nach rechts unten.

Aufgabe 4

Modellieren Sie den folgenden Graphen als Adjazenzmatrix. Lösung

Aufgabe 5

Zeichne eine graphische Darstellung des durch die folgende Adjazenzmatrix gegebenen Graphen:

	A	B	C	D	E
A		8		5
B			6
C		2		4	1
D	5
E			4

Lösung

Modellierung von Graphen durch Adjazenzmatrizen

Graphen werden in Java-Programmen oft implementiert, indem man ihre Adjazenzmatrix in einem zweidimensionalen Integer-Array speichert.

Zweidimensionales int-Array?

Du erinnerst Dich vielleicht noch an eindimensionale Arrays, z.B.

int[] zahlen = new int[7];   //Das Array zahlen enthält 7 Elemente: zahlen[0] bis zahlen[6].
zahlen[0] = 12;              // speichert im ersten Element die Zahl 12
zahlen[5] = 4;               // speichert im 6. Element die Zahl 4;
println(zahlen[5]);   // Gibt das 6. Element aus

Falls Du Dein Wissen über Arrays auffrischen möchtest, schau' Dir die Wiki-Seite aus Jgst. 10 dazu an!

Hier zur Wiederholung eine kleine Fingerübung zu eindimensionalen Arrays (Umkehrung eines Arrays).
Ein zweidimensionales Array speichert "ein Schachbrett voller Zahlen". Die Speicherung von bspw. $4 \times 3$ Zahlen geht so:

int[][] zahlen = new int[4][3];    // Der erste Index geht von 0 bis 3, der zweite von 0 bis 2
zahlen[2][1] = 10;
zahlen[0][2] = 14;

Man kann sich vorstellen, dass das Array zahlen aufgebaut ist wie ein Schachbrett. Der erste Index bezeichnet die Zeile des Feldes, der zweite die Spalte. Nach Ablauf dieses Programms sieht die Belegung des Arrays so aus:

zahlen	1	2
0	0	14
1	0	0
2	10	0
3	0	0

Im Array gespeichert sind natürlich nur die 12 Werte der blauen Zellen. Die fettgedruckten Zeilen- bzw. Spaltenköpfe dienen nur zur Veranschaulichung.

Beispiel 4 - Speicherung eines gerichteten Graphen

Das folgende Programm speichert den Graphen rechts als Adjazenzmatrix:

Die Klasse Graph

Wir entwickeln eine Klasse Graph, die nützliche Methoden zur Verwaltung und Analyse von Graphen bereitstellt.

Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung im Bild rechts.

Aufgaben:

Erstelle eine Methode void adjazenzmatrixAusgaben(), die die Adjazenzmatrix folgendermaßen auf dem Bildschirm ausgibt:

0 1 0
1 0 1
0 1 0

Erstelle eine Methode istIsoliert(int knoten), die genau dann true zurückgibt, wenn der Knoten isoliert ist (Definition siehe oben).

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 anderen 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: