Adjazenzliste – Wikipedia

Datenstruktur, die ein Diagramm darstellt

Dieser ungerichtete zyklische Graph kann durch die drei ungeordneten Listen beschrieben werden {b, c}, {a, c}, {a, b}.

In der Graphentheorie und Informatik Adjazenzliste ist eine Sammlung ungeordneter Listen, die zur Darstellung eines endlichen Graphen verwendet werden. Jede Liste beschreibt die Menge der Nachbarn eines Scheitelpunkts im Diagramm. Dies ist eine von mehreren häufig verwendeten Darstellungen von Diagrammen zur Verwendung in Computerprogrammen.

Implementierungsdetails[edit]

Eine Adjazenzlistendarstellung für einen Graphen ordnet jeden Scheitelpunkt im Graphen der Sammlung seiner benachbarten Scheitelpunkte oder Kanten zu. Es gibt viele Variationen dieser Grundidee, die sich darin unterscheiden, wie sie die Zuordnung zwischen Scheitelpunkten und Sammlungen implementieren, wie sie die Sammlungen implementieren, ob sie sowohl Scheitelpunkte als auch Kanten oder nur Scheitelpunkte als erstklassige Objekte enthalten und in welchen Arten von Objekten werden verwendet, um die Eckpunkte und Kanten darzustellen.

• Eine von Guido van Rossum vorgeschlagene Implementierung verwendet eine Hash-Tabelle, um jeden Scheitelpunkt in einem Diagramm einem Array benachbarter Scheitelpunkte zuzuordnen. In dieser Darstellung kann ein Scheitelpunkt durch ein beliebiges hashbares Objekt dargestellt werden. Es gibt keine explizite Darstellung von Kanten als Objekte.^[1]
• Cormen et al. schlagen eine Implementierung vor, bei der die Eckpunkte durch Indexnummern dargestellt werden.^[2] Ihre Darstellung verwendet ein Array, das durch die Scheitelpunktnummer indiziert ist, wobei die Arrayzelle für jeden Scheitelpunkt auf eine einfach verknüpfte Liste der benachbarten Scheitelpunkte dieses Scheitelpunkts zeigt. In dieser Darstellung können die Knoten der einfach verknüpften Liste als Kantenobjekte interpretiert werden; Sie speichern jedoch nicht die vollständigen Informationen zu jeder Kante (sie speichern nur einen der beiden Endpunkte der Kante), und in ungerichteten Diagrammen gibt es zwei verschiedene verknüpfte Listenknoten für jede Kante (einen innerhalb der Listen für jede der beiden Endpunkte der Kante).
• Die von Goodrich und Tamassia vorgeschlagene objektorientierte Inzidenzlistenstruktur weist spezielle Klassen von Scheitelpunktobjekten und Kantenobjekten auf. Jedes Scheitelpunktobjekt verfügt über eine Instanzvariable, die auf ein Sammlungsobjekt verweist, das die benachbarten Kantenobjekte auflistet. Jedes Kantenobjekt zeigt wiederum auf die beiden Scheitelpunktobjekte an seinen Endpunkten.^[3] Diese Version der Adjazenzliste verwendet mehr Speicher als die Version, in der benachbarte Scheitelpunkte direkt aufgelistet werden. Das Vorhandensein expliziter Kantenobjekte ermöglicht jedoch zusätzliche Flexibilität beim Speichern zusätzlicher Informationen zu Kanten.

Operationen[edit]

Die Hauptoperation, die von der Datenstruktur der Adjazenzliste ausgeführt wird, besteht darin, eine Liste der Nachbarn eines gegebenen Scheitelpunkts zu melden. Unter Verwendung einer der oben beschriebenen Implementierungen kann dies in konstanter Zeit pro Nachbar durchgeführt werden. Mit anderen Worten, die Gesamtzeit, um alle Nachbarn eines Scheitelpunkts zu melden v ist proportional zum Grad von v.

Es ist auch möglich, aber nicht so effizient, Adjazenzlisten zu verwenden, um zu testen, ob eine Kante zwischen zwei angegebenen Eckpunkten existiert oder nicht. In einer Adjazenzliste, in der die Nachbarn jedes Scheitelpunkts unsortiert sind, kann das Testen auf das Vorhandensein einer Kante in einer Zeit proportional zum Mindestgrad der beiden gegebenen Scheitelpunkte durchgeführt werden, indem eine sequentielle Suche durch die Nachbarn dieses Scheitelpunkts verwendet wird. Wenn die Nachbarn als sortiertes Array dargestellt werden, kann stattdessen eine binäre Suche verwendet werden, wobei die Zeit proportional zum Logarithmus des Grades ist.

Kompromisse[edit]

Die Hauptalternative zur Adjazenzliste ist die Adjazenzmatrix, eine Matrix, deren Zeilen und Spalten durch Scheitelpunkte indiziert sind und deren Zellen einen Booleschen Wert enthalten, der angibt, ob zwischen den Scheitelpunkten, die der Zeile und Spalte der Zelle entsprechen, eine Kante vorhanden ist. Für einen spärlichen Graphen (bei dem die meisten Eckpunktpaare nicht durch Kanten verbunden sind) ist eine Adjazenzliste wesentlich platzsparender als eine Adjazenzmatrix (als zweidimensionales Array gespeichert): Die Raumnutzung der Adjazenzliste ist proportional auf die Anzahl der Kanten und Scheitelpunkte im Diagramm, während für eine auf diese Weise gespeicherte Adjazenzmatrix der Raum proportional zum Quadrat der Anzahl der Scheitelpunkte ist. Es ist jedoch möglich, Adjazenzmatrizen platzsparender zu speichern, was der linearen Raumnutzung einer Adjazenzliste entspricht, indem eine durch Scheitelpunktpaare indizierte Hash-Tabelle anstelle eines Arrays verwendet wird.

Der andere signifikante Unterschied zwischen Adjazenzlisten und Adjazenzmatrizen besteht in der Effizienz der von ihnen ausgeführten Operationen. In einer Adjazenzliste können die Nachbarn jedes Scheitelpunkts effizient aufgelistet werden, und zwar zeitlich proportional zum Grad des Scheitelpunkts. In einer Adjazenzmatrix benötigt diese Operation Zeit proportional zur Anzahl der Scheitelpunkte im Diagramm, die erheblich höher als der Grad sein kann. Andererseits ermöglicht die Adjazenzmatrix das Testen, ob zwei Eckpunkte in konstanter Zeit nebeneinander liegen; Die Adjazenzliste ist langsamer, um diesen Vorgang zu unterstützen.

Datenstrukturen[edit]

Zur Verwendung als Datenstruktur ist die Adjazenzmatrix die Hauptalternative zur Adjazenzliste. Da jeder Eintrag in der Adjazenzmatrix nur ein Bit benötigt, kann er sehr kompakt dargestellt werden und nur belegt werden |V.|²/ 8 Bytes zusammenhängenden Raums, wo |V.| ist die Anzahl der Eckpunkte des Diagramms. Diese Kompaktheit vermeidet nicht nur Platzverschwendung, sondern fördert auch die Referenzlokalität.

Für ein spärliches Diagramm benötigen Adjazenzlisten jedoch weniger Platz, da sie keinen Platz für die Darstellung nicht vorhandener Kanten verschwenden. Bei Verwendung einer naiven Array-Implementierung auf einem 32-Bit-Computer erfordert eine Adjazenzliste für einen ungerichteten Graphen ungefähr 2 · (32/8) |E.| = 8 |E.| Bytes Speicherplatz, wo |E.| ist die Anzahl der Kanten des Diagramms.

Beachten Sie, dass ein ungerichteter einfacher Graph höchstens haben kann (|V.|²– |V.|) / 2 ≈ V. ² Kanten, die Schleifen zulassen, können wir lassen d = |E.| / |V.|² bezeichnen die Dichte des Graphen. Dann, 8 |E.| > |V.|²/ 8 wann |E.| / |V.|² > 1/64Das heißt, die Adjazenzlistendarstellung nimmt mehr Platz ein als die Adjazenzmatrixdarstellung, wenn d > 1/64. Daher muss ein Graph spärlich genug sein, um eine Darstellung der Adjazenzliste zu rechtfertigen.

Neben dem Platzkompromiss erleichtern die unterschiedlichen Datenstrukturen auch unterschiedliche Operationen. Das Finden aller Scheitelpunkte neben einem bestimmten Scheitelpunkt in einer Adjazenzliste ist so einfach wie das Lesen der Liste. Bei einer Adjazenzmatrix muss stattdessen eine ganze Zeile gescannt werden, was dauert Ö(|V.|) Zeit. Ob es eine Kante zwischen zwei gegebenen Scheitelpunkten gibt, kann gleichzeitig mit einer Adjazenzmatrix bestimmt werden, während Zeit proportional zum Mindestgrad der beiden Scheitelpunkte mit der Adjazenzliste benötigt wird.

Verweise[edit]

Weiterführende Literatur[edit]

Externe Links[edit]