Adjazenzliste - LinkFang.de





Adjazenzliste


In der Graphentheorie sind Adjazenzlisten (oder auch Nachbarschaftslisten) eine Möglichkeit Graphen zu repräsentieren. Dabei wird für jeden Knoten eine Liste, die Adjazenzliste, aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) angegeben. Oft basieren Datenstrukturen für Graphen auf Adjazenzlisten. Im einfachsten Fall wird in einem Array für jeden Knoten eine einfach verkettete Liste aller Nachbarn gespeichert.

Definition

Bei einem ungerichteten Graphen [math]G =\left(V, E \right)[/math] versteht man unter einer Adjazenzliste für einen Knoten [math]v \in V[/math] eine Liste aller Nachbarn von [math]v[/math], d.h. eine Liste der Knoten [math]\left\{ v' \in V: \{v, v'\} \in E \right\}[/math].

Bei einem gerichteten Graphen [math]G =\left(V, E \right)[/math] versteht man unter einer Adjazenzliste für einen Knoten [math]v \in V[/math] eine Liste aller Nachfolger von [math]v[/math], d.h. eine Liste der Knoten [math]\left\{ v' \in V: (v, v') \in E \right\}[/math].

In beiden Fällen ist die Reihenfolge der Knoten in der Adjazenzliste beliebig. Eine Adjazenzlisten-Repräsentation eines Graphen erhält man indem man für jeden Knoten eine Adjazenzliste angibt.

Beispiel 1

Ein ungerichteter Graph mit Knoten [math]V=\{a,b,c,d,e\}[/math] und Kanten [math]\{a,b\}, \{a,d\}, \{a,d\}, \{a,e\}, \{b,c\}, \{c,d\}[/math], und seine Repräsentation mit Hilfe von Adjazenzlisten.

Graph Adjazenzlisten
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a

Beispiel 2

Ein gerichteter Graph mit Knoten [math]V=\{a,b,c,d,e\}[/math] und Kanten [math](a,b), (a,d), (a,e), (a,b), (b,c), (c,d), (d,a)[/math], und seine Repräsentation mit Hilfe von Adjazenzlisten.

Graph Adjazenzlisten
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 

Adjazenzlisten als Datenstrukturen

Die Adjazenzlisten-Repräsentation von Graphen dient oft als Basis von Datenstrukturen für Graphen. Es gibt unterschiedliche Varianten diese Adjazenzlisten-Repräsentation in einer Datenstruktur umzusetzen, die auch unterschiedliche Verhalten der Datenstrukturen verursachen.

Einige Varianten:

  • Knoten-Array mit Adjazenzlisten als verkettete Listen: Hier wird ein mit Knotenidentifikatoren indiziertes Array gespeichert wobei in jedem Element des Arrays ein Zeiger auf die entsprechende Adjazenzliste gespeichert wird. Die Adjazenzlisten selbst werden als verkettete Listen gespeichert.
  • Verketteten Liste von Knoten mit Adjazenzlisten als verkettete Listen: Die Knoten werden als verkettete Liste gespeichert und jeder Knoten enthält einen Zeiger auf die entsprechende Adjazenzliste. Die Adjazenzlisten selbst werden auch als verkettete Listen gespeichert.

Beispiele

Knoten-Array mit Adjazenzlisten als einfach verkettete Listen

Graph Adjazenzlisten Datenstruktur
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 

Knoten-Array mit Adjazenzlisten als doppelt verkettete Listen

Graph Adjazenzlisten Datenstruktur
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 

Verketteten Liste von Knoten mit Adjazenzlisten als einfach verkettete Listen

Graph Adjazenzlisten Datenstruktur
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 

Siehe auch

Literatur

Weblinks


Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Adjazenzliste (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.