Nachdem wir uns mit der grundlegenden Struktur des Graphen beschäftigt haben, stellt sich die Frage, wie wir dies mit dem Computer umsetzen können. Die zentrale Frage stellt sich darin, wie die „Nachbarn“ eines KNOTEN im GRAPH gespeichert werden können. Dabei gibt es zwei zentrale Ansätze:
- Speichern der KANTEN von einem KNOTEN in einer Art Liste mit den Gewichtungen
- Eine zentrale Tabelle, in der die Verbindungen von KNOTEN zu KNOTEN aufgeführt sind.
Beide Ansätze haben ihre eigenen Anwendungsbereiche. Vergleichen wir die beiden Ansätze an einem Beispiel.
Die Adjazenzliste
Bei der Liste wird jede Kante vom Startknoten vorne aufgezählt. Dadurch ist die Liste eher schwer zu lesen.
- Mü: -(163)->Nü -(117)->Re
- Nü: -(80)→ Re -(163)→ Mü
- Re: -(80)→ Nü -(117)→ Mü
| Mü | Nü | Re | |
| Mü | 0 | 163 | 117 |
| Nü | 163 | 0 | 80 |
| Re | 117 | 80 |
Die Adjazenzmatrix
In der Adjazenzmatrix wird jede Kante in einer Art Tabelle gespeichert. Dabei ließt man die Tabelle von Zeile zur Spalte also ist die markierte Zelle die Kante von München nach Regensburg.
Die Adjazenzmatrix speichert fehlende Kanten meist mit dem Wert 0. Nur dann wenn im Sachzusammenhang eine Kantengewichtung von 0 sinnvoll ist, verwendet man die -1. Wir sehen sofort, dass ein ungerichteter Graph eine symmetrische Tabelle erzeugt. Beim ungewichteten Graph wird jede KANTE die existiert mit Gewicht 1 angegeben. Jedes Element der Matrix wird mit einem Indexpaar identifiziert. In unserem Beispiel wäre von München(0) nach Regensburg(2) der Matrixeintrag in der rechten oberen Ecke und hätte den Bezeichner matrix[0][2].
Ein Graph kann durch eine Tabelle, die alle Kanten zwischen den Knoten speichert dargestellt werden. Man nennt dies die Adjazenzmatrix des Graphen. Man ließt die Matrix von Zeile zu Spalte.
Merksatz 1.2.1
Umsetzung in Java
Um die Knoten eines Graphen zu speichern kann man einfach ein Feld verwenden. In den üblichen Anwendungen weiß man vorher, wie viele Knoten man hat. Daher ist es nicht nötig eine Liste zu verwenden. Zur Erinnerung:
KNOTEN[] k;
//Im Konstruktor
k = new KNOTEN[3]; //Für 3 Knoten
k[0].Zeichnen();
...Die Adjazenzmatrix können wir ähnlich lösen. Die Idee ist, jede Zeile als ein Feld zu speichern und dann alle Zeilen in einem Feld von Feldern zu speichern. Das bedeutet für unseren Code folgendes:
//Atrribut der Adjazenzmatrix
int[][] matrix;
//Im Konstruktor
matrix = new int[3][3]; //Für 3x3 Matrix
matrix[0][0] = 0;
...Man speichert die Knoten des Graphen in einem Feld der Klasse KNOTEN. Die Adjazenzmatrix kann mit einem zweidimensionalem Feld der Datentyps
Merksatz 1.2.2int[][]abgebildet werden.
Aufgabe 1:
Erstellen Sie den Graph zur gegebenen Adjazenzmatrix (links) und die Adjazenzmatrix zum Graphen auf der rechten Seite. Woran kann man in der Adjazenzmatrix erkennen ob der Graph gerichtet ist?
| 0 | 0 | 5 | 0 |
| 3 | 0 | 3 | 0 |
| 5 | 5 | 2 | 3 |
| 1 | 2 | 2 | 0 |
Aufgabe 2:
Geben Sie jeweils eine Adjazenzmatrix an, die zu einem Graphen mit fünf Knoten passt der…
- … einen unerreichbaren Konten hat.
- … schwach aber nicht stark zusammenhängend ist.
Aufgabe 3:
Implementieren Sie einen Graphen mit Adjazenzmatrix anhand folgender Checkliste:
Klasse STADT
- Attribut für Namen der Stadt
- Konstruktor, der den Namen setzt
- Getter und Setter für die Klasse
Klasse KNOTEN
- Speichert eine STADT
- Methode zum Setzen/Ausgeben der STADT
Klasse GRAPH
- Feld mit KNOTEN
- zweidimensionales Feld matrix
- Methode: KnotenAnzeigen() (Konsolenausgabe)
- Methode: MatrixAnzeigen() (Konsolenausgabe)
Wissen auf Deutsch 