Adjazenzliste

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Graphentheorie sind Adjazenzlisten (oder auch Nachbarschaftslisten) eine Möglichkeit Graphen zu repräsentieren. Dabei wir 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[Bearbeiten]

Bei einen 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 einen 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[Bearbeiten]

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

Graph Adjazenz Listen
Ein ungerichteter Graph
 a: d, b, d, e
 b: c, a
 c: b, d 
 d: a, a, c
 e: a

Beispiel 2[Bearbeiten]

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

Graph Adjazenz Listen
Ein ungerichteter Graph
 a: b, d, e
 b: c
 c: d 
 d: a
 e: 

Literatur[Bearbeiten]

Weblinks[Bearbeiten]