Adjazenzmatrix

Die bisher 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 1

(Adjazenzmatrix eines gerichteten Graphen)

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

Beispiel 2

	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 1

Modellieren Sie den folgenden Graphen als Adjazenzmatrix. Lösung

Aufgabe 2

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

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

Lösung

Aufgabe 3

Ein Graph ist durch die folgende Adjazenzmatrix gegebenen:

	A	C	D	E
A	1	1	1	0
B	0	0	0	0
C	1	1	0	0
D	0	0	0	1
E	0	1	0	0

Bewerten Sie die Aussagen:

Der Graph ist gewichtet.
Der Graph ist gerichtet.
Es gibt einen Pfad von D nach A.
Der Graph ist zyklisch.
Es gibt mindestens einen Knoten, der eine Kante auf sich selbst hat (d.h. eine Kante, die von diesem Knoten ausgeht und auf diesen Knoten zeigt).
Es gibt einen isolierten Knoten.

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).