Kleines Nachschlagewerk Informatik
Speicherung von Graphen
Worum geht es?
Möchte man, dass Programme Graphen ver- und bearbeiten, muss man sie natürlich speichern. Es muss also im Computer eine sinnvolle Datenstruktur geben, welche Knoten und Kanten verwaltet. Es sind viele verschiedene Möglichkeiten denkbar, zwei Varianten haben sich aber durchgesetzt: die Speicherung mit Listen und die Speicherung mit Matrizen.
Adjazenzlisten
Die Adazenzliste speichert einen Graphen als zweidimensionale Liste. Basis ist eine Liste mit allen Knoten. Jeder Knoten hat wiederum eine Liste, die sich die Knoten merkt, mit denen dieser Knoten verbunden ist.

Die Wichtung der Kanten speichert man in den Knoten der Subliste.
Beispiel Liste
Folgendes Bild zeigt rechts einen Graphen und links ein Objektdiagramm der Liste.





Es wurde hier von einer Liste gesprochen, man kann aber auch Arrays zur Speicherung nehmen. Jeder Knoten ist ein Objekt. Sind also Listen etc. als Datenstruktur vorhanden, braucht man nur noch eine Knotenklasse.
Implementation von Adjazenzlisten
Möchte ein Knoten Name, Nachfolger in der Liste, alle verbundenen Knoten und die Wichtung speichern, so kann eine Klasse im einfachsten Fall so aussehen.



Adjazenzmatrizen
Eine andere Alternative der Speicherung ist die der Adjazenzmatrix. Matrizen sind zweidimensionale Zahlenfelder und werden somit als zweidimensionales Array gespeichert. Diese Matrizen sind quadratisch und und ihre Dimension ist so groß wie die Anzahl der Knoten.

Adjazenzmatrizen sind so zu lesen: Die Zahl in der k-ten Zeile und n-ten Spalte gibt an, ob es eine Verbindung vom k-ten zum n-ten Knoten gibt und evtl. wie lang diese Verbindung ist.

Ist der Graph ungewichtet, gibt es nur Nullen und Einsen. Haben die Kanten Wichtungen (z.B. Straßenlängen), dann stehen statt der Einsen die konkreten Längen in der Matrix.
Beispiel Matrix
Nimmt man den Graph aus dem Beispiel der Adjazenzliste, ergibt sich folgende Matrix.

Implementation von Adjazenzmatrizen
Zur Speicherung der Verbindungen braucht man ein zweidimensionales Array. Da dieses Array nur die Verbindungen speichert, braucht man trotz allem noch eine Liste, in welcher die Knoten gespeichert werden. Im Gegensatz zur Adjazenzliste ist diese Liste jedoch eindimensional. Die Reihenfolge in der Liste entspricht der Reihenfolge im Array.
Zur Beachtung
Für Matrizen gilt: