Kurs:Algorithmen und Datenstrukturen/Vorlesung/Repräsentation Graphen




Repräsentation von Graphen

Bearbeiten

Auf dieser Seite wird die Repräsentation von Graphen behandelt. Wir fragen uns wie effizient die Datenstruktur für Graphen ist.

Kanten- und Knotenlisten

Bearbeiten

Bei durchnummerierten Knoten erfolgt eine einfache Realisierung. Historisch gesehen ist es die erste verwendete Datenstruktur. Außerdem ist sie als Austauschformat geeignet und die Auflistung ist nach Knoten oder nach Kanten sortiert.

Beispiel Kantenliste

Bearbeiten
 
Graph

Gegeben ist eine Kantenliste für  

Die erste Zahl (6) steht für die Knotenzahl. Die zweite Zahl (11) steht für die Kantenzahl. Die weiteren Paare (1,2 ; 1,3...) stehen für die Kanten.

6,11,1,2,1,3,3,1,4,1,3,4,3,6,5,3,5,5,6,5,6,2,6,4

Beispiel Knotenliste

Bearbeiten
 
Graph

Gegeben ist eine Knotenliste für  

6,11,2,2,3,0,3,1,4,6,1,1,2,3,5,3,2,4,5 Die Teilfolge 2,2,3 bedeutet, dass der Knoten 1 den Ausgangsgrad 2 hat und herausgehende Kanten zu den Knoten 2 und 3.






Vergleich Kanten-und Knotenliste

Bearbeiten

Falls ein Graph mehr Kanten als Knoten hat (=„Normalfall“),benötigen Knotenlisten weniger Speicherbedarf als Kantenlisten. Das bedeutet für die Kantenlisten gilt   und für die Knotenliste gilt  .

Adjazenzmatrix

Bearbeiten

Adjazenz bedeutet berühren oder aneinander grenzen. Hier werden die Graphen als Boole‘sche Matrix dargestellt. 1-Einträge werden für direkte Nachbarschaften verwendet. A ist eine Adjazenzmatrix für den Graph  

Beispiel

Bearbeiten
 
Graph

 

Eigenschaften

Bearbeiten

Bei ungerichteten Graphen reicht eine Halbmatrix (ein Dreieck) aus. Bei gewichteten Graphen werden Gewichte statt Boolsche Werte genutzt. Der Vorteil einer Adjazenzmatrix ist, dass einige Graphenoperationen als Matrixoperation möglich sind. So ist sie beispielsweise durch iterierte Matrixmultiplikation erreichbar und besitzt schöne Eigenschaften für die mathematische Analyse.

     

So sieht die Darstellung als Dreiecksmatrix aus. Die Diagonale kann ebenfalls weggelassen werden, wenn Schleifen verboten sind.

Adjazenzliste

Bearbeiten

Wir haben eine Liste der 3b oder alternativ ein Array. Pro Knoten werden die von ihm ausgehenden Kanten als Liste, welche besonders geeignet für dünn besetzte Matrizen sind, oder als Array von Zeigern dargestellt. Der Graph wird durch |V|+1 verkettete Listen realisiert. In Adjazenzlisten sind dynamische Erweiterungen im Sinne verketteter Listen erlaubt. Knotenlisten können natürlich auch als verkettete Listen realisiert werden.

 
Graph

 

Speicherbedarf

Bearbeiten

Seien n=|V| und m=|E|. Benötigt werden insgesamt   Listenelemente. ag(i) ist die Anzahl der Nachbarn von i (gerichtet).

Transformation zwischen den Darstellungen

Bearbeiten

Die vorgestellten Realisierungsvarianten sind äquivalent. Jede Darstellung kann in jede andere ohne Informationsverlust transformiert werden. Dafür wird die eigene Darstellung ausgelesen und anschließend die andere Darstellung erzeugt. Der Aufwand dieser Transformationen variiert von O(n+m) bis   wobei im schlechtesten Fall   gilt.   tritt immer auf, wenn eine naive Matrixdarstellung beteiligt ist. Nicht naive Darstellungen sind für sehr dünn besetzte Matrizen nötig.

Komplexitätsbetrachtung

Bearbeiten

Bei Kantenlisten ist das Einfügen von Kanten (Anhängen von zwei Zahlen) und von Knoten (Erhöhung der ersten Zahl um 1) besonders günstig. Das Löschen von Kanten zieht das Verschieben der nachfolgenden Kanten mit sich und die Knoten müssen neu nummeriert werden.

Bei Knotenlisten ist das Einfügen von Knoten, also die Erhöhung der ersten Zahl und das Anhängen einer 0, günstig.

Bei der Matrixdarstellung ist das Manipulieren von Kanten sehr effizient ausführbar. Der Aufwand beim Knoteneinfügen hängt von der Realisierung ab. Im worst case wird die Matrix in eine größere Matrix kopiert.

Bei Adjazenzlisten gibt es unterschiedlichen Aufwand, je nachdem, ob die Knotenliste ein Feld mit Direktzugriff oder eine verkettete Liste mit sequenziellem Durchlauf realisiert.

Operation Kantenliste Knotenliste Adjazenzmatrix Adjazenzliste
Einfügen Kanten Beta(1) O(n+m) O(1) O(1)/O(n)
Löschen Kanten O(m) O(n+m) O(1) O(n)
Einfügen Knoten O(1) O(1)   O(1)
Löschen Knoten O(m) O(n+m)   O(n+m)

Das Löschen eines Knotens impliziert für gewöhnlich auch das Löschen der dazugehörigen Kanten.