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

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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

Adjazensmatrix

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.

Ungerichtet2 Ungerichtet Ungerichtet3

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

Adjazenzliste

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg