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 G=\left(V,E\right) versteht man unter einer Adjazenzliste für einen Knoten v\in V eine Liste aller Nachbarn von v, d.h. eine Liste der Knoten \left\{v'\in V:\{v,v'\}\in E\right\}.

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

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 V=\{a,b,c,d,e\} und Kanten {\displaystyle E=\{\{a,b\},\{a,d\},\{a,d\},\{a,e\},\{b,c\},\{c,d\}\}}, und seine Repräsentation mit Hilfe von Adjazenzlisten.

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

Beispiel 2

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

Graph Adjazenzlisten
Ein gerichteter Graph
 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:

Beispiele

Knoten-Array mit Adjazenzlisten als einfach verkettete Listen

Graph Adjazenzlisten Datenstruktur
Ein ungerichteter Graph
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
Adjacencylist array of linkedlists undirectedgraph.svg
Ein gerichteter Graph
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 
Adjacencylist array of linkedlists directedgraph.svg

Knoten-Array mit Adjazenzlisten als doppelt verkettete Listen

Graph Adjazenzlisten Datenstruktur
Ein ungerichteter Graph
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
Adjacencylist array of doublelinkedlists undirectedgraph.svg
Ein gerichteter Graph
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 
Adjacencylist array of doublelinkedlists directedgraph.svg

Verketteten Liste von Knoten mit Adjazenzlisten als einfach verkettete Listen

Graph Adjazenzlisten Datenstruktur
Ein ungerichteter Graph
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a
Adjacencylist linkedlistof linkedlists undirectedgraph.svg
Ein gerichteter Graph
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 
Adjacencylist linkedlistof linkedlists directedgraph.svg

Siehe auch

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 17.05. 2020