Adjazenzliste

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

Die Adjazenzliste (oder auch Nachbarschaftsliste) ist eine Möglichkeit, Graphen im Computer zu speichern. Sie wird in ihrer einfachsten Form durch eine einfach verkettete Liste aller Knoten des Graphen dargestellt, wobei jeder Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) besitzt. Vielfachheiten der Kanten, Knotengewichte, und Kantengewichte werden meist in Attributen der einzelnen Elemente gespeichert. Je nach Problemstellung kann es notwendig sein, statt einer einfach verketteten Liste eine doppelt verkettete Liste zu verwenden und in gerichteten Graphen zusätzlich zur Liste der Nachfolger eine Liste der Vorgänger zu verwalten. Sie ist in der Praxis meist die kanonische Darstellung von Graphen, da sich viele graphentheoretische Probleme nur mit Adjazenzlisten in linearer Zeit lösen lassen.

Definition[Bearbeiten]

Mit V als Menge der Knoten und E als Menge der Kanten sei ein Graph G =\left(V, E \right) (ohne Mehrfachkanten) gegeben. Das heißt es ist E\subset V\times V und es ist (x,y)\in E genau dann, wenn der Graph eine Kante von x nach y enthält. Zu jedem Knoten x\in V ist die Adjazenzliste definiert als

A(x)=\left\{ y \in V: (x, y) \in E \right\},

das heißt A(x) ist für jeden Knoten x die Liste aller Nachbarn (bzw. Nachfolger) y.

Literatur[Bearbeiten]