Graphrepräsentationen WS13-14
Inhaltsverzeichnis |
Grundbegriffe der Graphentheorie
Datenstrukturen für Graphen
Auswahl - Operationen für Graphen
Die Wahl der Darstellung eines Graphen muss immer im Bezug auf die mit den Daten durchzuführenden Operationen erfolgen. Die Operationen sind problemabhängig. Die wichtigsten Operationen für Graphen sind:
- Feststellen, ob ein Paar von Ecken benachbart ist.
- Bestimmung der Nachbarn einer Ecke.
- Bestimmung der Nachfolger und Vorgänger einer Ecke in einem gerichteten Graphen.
Neben der Effizienz der Operationen spielt auch der Speicherplatzverbrauch eine große Rolle bei der Wahl einer Datenstruktur. Hierbei stellt man häufig Wechselwirkungen zwischen Speicherplatzverbrauch und Effizienz fest. Eine sehr effiziente Erledigung der Operation benötigt oft mehr Speicherplatz, als eine weniger effiziente. Weiterhin muss Beachtung finden, ob es sich um eine statische oder eine dynamische Anwendung handelt. Bei dynamischen Anwendungen wird der Graph verändert, hierbei benötigt man Operationen zum Löschen und Einfügen von Ecken und Kanten. Oft sollen nur Graphen mit einer speziellen Eigenschaft (z.B. ohne geschlossene Wege) dargestellt werden. In diesen Fällen kann man durch die Wahl einer spezialisierten Datenstruktur die Effizienz weiter steigern.
Kantenliste
Adjazenzliste
Der Graph wird bei einer Adjazenzliste dadurch dargestellt, dass für jede Ecke die Liste der Nachbarn abgespeichert wird. Es lassen sich gerichtete und ungerichtete Graphen darstellen.
Der Speicheraufwand ist abhängig von der Anzahl der Kanten.
Adjazenzmatrix
Um einen Graph G darzustellen bietet sich eine n \cdot n Matrix A(G) an. Hierbei ist der Eintrag a_{ij} von A(G) gleich 1, wenn es eine Kante von i nach j gibt, andernfalls gleich 0. Da diese Matrix direkt die Nachbarschaft der Ecken widerspiegelt, nennt man sie Adjazenzmatrix. Zwei benachberte Knoten werden als adjazent bezeichnet. Da die Einträge der Matrix nur die Werte 0 und 1 annehmen können, kann A(G) als Boolsche Matrix dargestellt werden. Es lassen sich sowohl gerichtete und ungerichtete Graphen darstellen, wobei im letzten Fall die Adjazenzmatrizen symmetrisch sind.
Ist ein Diagonaleintrag der Matrix gleich 1, so bedeutet dies, dass eine Schlinge vorhanden ist. Um festzustellen ob es einen Weg von i nach j gibt, muss man nur den Eintrag a_{ij} betrachten. Diese Operation kann somit unabhängig von der Größe der Matrix in einem Schritt durchgeführt werden. Um die Nachbarn einer Ecke i in einem ungerichteten Graphen festzustellen, müssen alle Einträge der i-ten Spalte oder der i-ten Zeile durchsucht werden. Diese Operation ist somit unabhängig von der Anzahl der Nachbarn des Knotens. Für das Auffinden von Vorgängern und Nachfolgern gilt eine analoge Aussage. Im ersten Fall wird die passende Spalte und im zweiten die passende Zeile durchsucht.
Unabhängig von der Anzahl der Kanten, werden immer n^2 Speicherplätze benötigt. Da bei einem ungerichteten Graphen, die Adjazenzmatrix symmetrisch ist, reicht es in diesem Fall die Einträge oberhalb der Diagonale zu speichern. Dann benötigt man noch \frac{n \cdot(n-1)}{2} Speicherplätze.