11 – Datenstrukturen für Graphen

 

Im Rechner können Graphen durch verschiedene Datenstrukturen beschrieben werden. Im einfachsten Fall läßt sich ein Graph durch eine Matrix (sogenannte Adjazenzmatrix) beschreiben, in der jedem Knoten eine Spalte und eine Zeile zugeordnet ist.

Adjazenzmatrix

In der folgenden Abbildung ist als Beispiel ein Graph abgebildet:

Seine Darstellung als Adjazenzmatrix sieht aus wie folgt (es wird angenommen, dass auch ein Weg von vi zu vi für jedes i besteht):

A = \left( {\begin{array}{*{20}{c}}    1 & 1 & 1 &   \\    1 & 1 & 1 &   \\    1 & 1 & 1 & 1  \\     &  & 1 & 1  \\  \end{array} } \right)

Alle Felder der Matrix, die leer gelassen sind, sind mit einer Null besetzt. Alle Felder, die eine 1 enthalten, stellen eine Verknüpfung zwischen den beiden zugehörigen Knoten her. Der oben dargestellte Graph ist ungerichtet, so dass jede Kante zweimal auftaucht, jeweils in beiden Richtungen. Die Adjazenzmatrix eines ungerichteten Graphen ist, wie man hier sieht, stets symmetrisch. Es würde also ausreichen, nur die obere rechte oder untere linke Hälfte der Matrix zu speichern.

Im Fall eines bewerteten Graphen könnte man anstelle der Einsen die Bewertung der Pfeile in die Adjazenzmatrix eintragen, z.B. die Längen der Wege zwischen den Knoten.

Es gilt für die Knotenmenge V und die Kantenmenge E:

{\text{Anzahl der Knoten: }}\left| V \right|

{\text{Anzahl der Kanten: }}\left| E \right|

{\text{max}}{\text{. Anzahl der Kanten: }}\left| E \right|_{\max }  = \left| V \right|+\left( {\left| V \right|-1} \right)+\ldots +1 = \frac{{\left| V \right| \cdot \left( {\left| V \right|-1} \right)}} {2}

Wenn selbstadjazente Knoten zugelassen sind, d.h. wenn es Wege von einem Knoten zu sich selbst geben kann, dann gilt stattdessen:

{\text{Anzahl der Knoten: }}\left| V \right|

{\text{Anzahl der Kanten: }}\left| E \right|

{\text{max}}{\text{. Anzahl der Kanten: }}\left| E \right|_{\max }  = \left| V \right|+\left( {\left| V \right|-1} \right)+\ldots +1 = \frac{{\left| V \right| \cdot \left( {\left| V \right|+1} \right)}} {2}

Dies entspricht der Anzahl der Einträge einer oberen rechten Dreiecksmatrix. Wenn der Graph gerichtet ist, ist die Matrix nicht mehr symmetrisch, daher kommt noch die untere linke Hälfte dazu:

\left| E \right|_{\max }  = \left| V \right|^2

Vorteile der Adjazenzmatrix

  • inzidente Kanten eines Knotens sind schnell bestimmbar
  • adjazente Knoten sind schnell bestimmbar

Nachteile der Adjazenzmatrix

  • nicht dynamisch, kann also nicht einfach vergrößert werden
  • der Speicherplatzbedarf beträgt O(|V|2) und ist daher nur für eng besetzte Matrizen angemessen.

Anmerkung:
Ein ungerichteter Graph kann durch eine symmetrische Adjazenzmatrix dargestellt werden, so lässt sich Speicherplatz sparen.

Einige andere wichtige Datenstrukturen für Graphen sind zwar wesentlich weniger speicherintensiv, lassen aber dafür keine so einfache Ermittlung inzidenter Kanten zu.

Kanten- und Knotenliste

Der selbe Graph wie im letzten Beispiel, nun als gerichteter Graph:

Der Graph kann wie folgt in zwei Listen gespeichert werden:

Knotenliste
\underbrace {\begin{array}{*{20}{c}}    Knoten & v_1  & v_2  & v_3  & v_4   \\   \end{array} }_{{\text{oder auch als Feld}}}

Wenn wir zu den Knoten noch andere Informationen, wie zum Beispiel geometrische Daten (Koordinaten) oder Knotenkosten speichern wollen, erweitern wir die Liste einfach um weitere Zeilen.

Weiterhin benötigen wir:

Kantenliste
\left. {\begin{array}{*{20}{c}}    von & 1 & 2 & 3 & 3 & 4  \\    nach & 2 & 3 & 1 & 4 & 3  \\   \end{array} } \right\}{\text{Verweise auf Knotenindizes}}

Alle Kanten sind in einer Liste bzw. Tabelle aufgeführt. Jede Kante verweist per Nummer auf einen Anfangs- und Endknoten. Die Nachbarschaftsrelationen des Graphen sind durch diese Darstellung in einer einzigen Liste vollständig beschrieben. Auch die geometrischen und sonstigen Zusatzattribute der Kante (Form, Strichstärke, Linienart, Farbe) können wir durch Hinzufügen weiterer Zeilen zur Kantentabelle in dieser Datenstruktur unterbringen.
Bei ungerichteten Graphen muss jede Kante auch noch in die andere Richtung eingetragen werden, wodurch sich die Listenlänge verdoppelt.

Vorteile der Kanten- und Knotenliste

  • speichereffizient auch für dünn besetzte Graphen
  • gewichtete Graphen können leicht durch eine zusätzliche Zeile “Bewertung” in der Knoten- bzw. Kantenliste realisiert werden
  • dynamische Datenstruktur, leicht erweiterbar

Nachteile der Kanten- und Knotenliste

  • inzidente Kanten finden (zum Beispiel alle Kanten finden, die an einen Knoten angrenzen) hat einen Rechenaufwand von O(|E|)
  • adjazente Knoten finden hat ebenfalls einen Rechenaufwand von O(|E|)

Adjazenzliste

Diese dritte Möglichkeit ist die beste und wird auch am häufigsten gebraucht, da sie die Vorteile der anderen beiden Möglichkeiten kombiniert.

Die Idee einer Adjazenzliste ist eine verkettete Liste der Knoten mit gespeicherten Informationen über erreichbare Nachbarn:

\begin{array}{*{20}{c}}    v_1  &  \to  & v_2 \left( {e_1 } \right) &   \\    v_2  &  \to  & v_3 \left( {e_2 } \right) &   \\    v_3  &  \to  & v_1 \left( {e_4 } \right), & v_4 \left( {e_3 } \right)  \\    {\underbrace {v_4 }_{Knoten}} &  \to  & v_3 \left( {e_5 } \right) &   \\   \end{array}

Vorteile der Adjazenzliste

  • adjazente Knoten sind schnell bestimmbar (Rechenaufwand = “Ausgangsgrad”, d.h. Anzahl der ausgehenden Kanten)
  • es ist leicht möglich, Kanten zu löschen
  • dynamische Datenstruktur, leicht erweiterbar

Nachteile der Adjazenzliste

  • inzidente Kanten finden (zum Beispiel alle Kanten finden, die an einen Knoten angrenzen) hat einen hohen Rechenaufwand
  • Knoten zu löschen ist deswegen ziemlich aufwändig