Hallo zusammen.
In diesem Artikel möchte ich die wichtigsten Datenstrukturen aufzählen, die in der Informatik zur Speicherung von Graphen verwendet werden, und außerdem von ein paar anderen solchen Strukturen erzählen, die sich mir irgendwie "kristallisiert" haben.
Fangen wir an. Aber nicht ganz am Anfang – ich denke, wir wissen bereits, was ein Graph ist und welche Typen es gibt (gerichtete, ungerichtete, gewichtete, ungewichtete, mit mehreren Kanten und Schleifen oder ohne).
Fangen wir an. Welche Möglichkeiten von Datenstrukturen für die "Graphenspeicherung" haben wir?
1. Matriziale Datenstrukturen
1.1 Adjazenzmatrix. Die Adjazenzmatrix ist eine Matrix, in der die Überschriften der Zeilen und Spalten den Nummern der Knoten des Graphen entsprechen. Der Wert jedes Elements a(i,j) wird durch das Vorhandensein oder Nichtvorhandensein von Kanten zwischen den Knoten i und j bestimmt. Es ist offensichtlich, dass bei einem ungerichteten Graphen eine solche Matrix symmetrisch ist, oder man kann sich darauf einigen, dass wir alle Werte nur oberhalb der Hauptdiagonale speichern. Für ungewichtete Graphen kann a(i,j) durch die Anzahl der Kanten von i nach j definiert werden (wenn es eine solche Kante nicht gibt, dann ist a(i,j) = 0), und für gewichtete Graphen entspricht es ebenfalls dem Gewicht (der Gesamtheit des Gewichts) der genannten Kanten.
1.2 Inzidenzmatrix. In diesem Fall wird unser Graph auch in einer Tabelle gespeichert, in der die Zeilennummern normalerweise den Nummern ihrer Knoten entsprechen und die Spaltennummern den vorab nummerierten Kanten. Wenn ein Knoten und eine Kante einander inzi-dent sind, wird in der entsprechenden Zelle ein Nicht-Null-Wert eingetragen (bei ungerichteten Graphen wird bei Inzidenz von Knoten und Kante eine 1 eingetragen, bei gerichteten Graphen „1“, wenn die Kante von einem Knoten „ausgeht“, und „-1“, wenn sie in ihn „hineingeht“ (das ist leicht zu merken, da das Zeichen „Minus“ auch gewissermaßen in die Zahl „-1“ „hineingeht“)). Bei gewichteten Graphen kann anstelle von 1 und -1 wieder das Gesamte-gewicht der Kante angegeben werden.
2. Aufzählende Datentypen
2.1 Nachbarschaftsliste. Hier scheint alles einfach zu sein. Jedem Knoten des Graphen kann im Allgemeinen jede aufzählende Struktur zugeordnet werden (Liste, Vektor, Array, ...), in der die Nummern aller benachbarter Knoten gespeichert werden. Bei gerichteten Graphen werden wir in eine solche Liste nur die Knoten eintragen, zu denen es eine „gerichtete“ Kante vom Merkmal-Knoten gibt. Bei gewichteten Graphen wird die Implementierung komplizierter.
2.2 Kantensliste. Eine ziemlich gängige Datenstruktur. Eine Kantensliste, wie der Name schon sagt, stellt einfach eine Liste der Kanten eines Graphen dar, wobei jede Kante durch einen Startknoten, einen Endknoten (bei ungerichteten Graphen ist die Reihenfolge hier nicht entscheidend, jedoch können zur Vereinheitlichung verschiedene Regeln verwendet werden, wie z. B. die Angabe der Knoten in aufsteigender Reihenfolge) und einem Gewicht (nur für gewichtete Graphen) definiert ist.
Bei den oben genannten Listen-Matrizen können Sie genauer nachsehen (und mit Illustrationen) zum Beispiel unter .
2.3 Nachbarschaftsarray. Eine nicht so häufig vorkommende Struktur. Im Wesentlichen ist es eine Art „Verpackung“ von Nachbarschaftslisten in eine einfache Struktur (Array, Vektor). Die ersten n (entsprechend der Anzahl der Knoten im Graphen) Elemente dieses Arrays enthalten die Startindizes desselben Arrays, ab denen alle Knoten, die diesem benachbart sind, als Folge aufgelistet sind.
Hier fand ich die klarste (für mich) Erklärung:
3. Nachbarschaftsvektor und Assoziatives Nachbarschaftsarray
Es kommt vor, dass der Autor dieser Zeilen, zwar kein professioneller Programmierer, aber hin und wieder mit Graphen in Berührung gekommen ist, meistens mit Kantenlisten zu tun hatte. Tatsächlich ist es praktisch, wenn ein Graph mehrere Schleifen und Kanten aufweist. Daher schlage ich vor, den klassischen Kantenlisten mehr Aufmerksamkeit zu schenken und deren "Entwicklung/Abzweigung/Modifikation/Mutation" zu berücksichtigen, insbesondere den Adjazenzvektor und das Adjazenzarray.
3.1 Adjazenzvektor
Fall (a1): ungewichteter Graph
Wir nennen den Adjazenzvektor für einen ungewichteten Graphen eine geordnete Menge von einer geraden Anzahl ganzer Zahlen (a[2i], a[2i+1],…, wobei i bei 0 beginnt), in der jedes Zahlenpaar a[2i], a[2i+1] eine Kante zwischen den Knoten a[2i] und a[2i+1] definiert.
Dieses Format enthält keine Informationen darüber, ob der Graph gerichtet ist (beide Varianten sind möglich). Bei Verwendung dieses Formats für einen Graphen wird angenommen, dass die Kante von a[2i] nach a[2i+1] gerichtet ist. Hier und im Folgenden: Für ungerichtete Graphen können bei Bedarf Anforderungen an die Reihenfolge der Knoten angewendet werden (zum Beispiel, dass der Knoten mit der kleineren zugewiesenen Nummer zuerst kommt).
In C++ ist es sinnvoll, den Nachbarschaftsvektor mit std::vector zu definieren, weshalb der Name dieser Datenstruktur gewählt wurde.
Fall (a2): ungewichteter Graph, Kantenwerte sind ganzzahlig.
Analog zu Fall (a1) bezeichnen wir den Nachbarschaftsvektor für einen gewichteten Graphen mit ganzzahligen Kantenwerten als eine geordnete Menge (dynamisches Array) von Zahlen (a[3i], a[3i+1], a[3i+2],…, wobei i von 0 zählt), wobei jedes "Triplet" a[3i], a[3i+1], a[3i+2] eine Kante zwischen den Knoten mit den Nummern a[3i] und a[3i+1] darstellt, während der Wert a[3i+2] das Gewicht dieser Kante ist. Dieser Graph kann sowohl gerichtet als auch ungerichtet sein.
Fall (b): ungewichteter Graph, Kantenwerte sind nicht ganzzahlig.
Da in einem Array (Vektor) keine heterogenen Elemente gespeichert werden können, ist beispielsweise die folgende Implementierung möglich. Der Graph wird in einem Paar von Vektoren gespeichert, wobei der erste Vektor der Nachbarliste des Graphen ohne Gewichtungen entspricht und der zweite Vektor die entsprechenden Gewichte enthält (mögliche Implementierung für C++: std::pair). Somit wäre für eine Kante, die durch das Paar der Knoten mit den Indizes 2i und 2i+1 des ersten Vektors definiert wird, das Gewicht das Element unter dem Index i des zweiten Vektors.
Warum ist das notwendig?
Nun, für den Autor dieser Zeilen schien es zur Lösung einiger Aufgaben ausreichend nützlich zu sein. Aus formaler Sicht ergeben sich damit folgende Vorteile:
- Der Nachbarvektor, wie jede andere ‘aufzählbare’ Struktur, ist relativ kompakt, benötigt weniger Speicherplatz als die Nachbarmatrix (bei spärlichen Graphen) und lässt sich relativ einfach implementieren.
- Die Knoten des Graphen können prinzipiell auch mit negativen Zahlen markiert werden. Vielleicht wird ein solcher ‘Schwachsinn’ ja benötigt.
- Graphen können mehrere Kanten und Schleifen enthalten, wobei diese unterschiedliche Gewichtungen haben können (positive, negative und sogar null). Hier gibt es keine Einschränkungen.
- Außerdem können Kanten unterschiedliche Eigenschaften zugewiesen werden – siehe dazu Punkt 4.
Allerdings ist es anzumerken, dass dieser „Listenansatz“ keinen schnellen Zugriff auf die Kante ermöglicht. Hier kommt das assoziative Nachbararray ins Spiel, dazu mehr im Folgenden.
3.2 Assoziatives Nachbararray
Wenn der Zugang zu einer bestimmten Kante, ihrem Gewicht und anderen Eigenschaften für uns entscheidend ist und die Anforderungen an den Speicher die Verwendung einer Nachbarmatrix nicht zulassen, sollten wir überlegen, wie wir den Nachbarvektor ändern können, um dieses Problem zu lösen. Der Schlüssel ist eine Kante des Graphen, die als geordnete Paar von Ganzzahlen dargestellt werden kann. Woran erinnert uns das? An den Schlüssel in einem assoziativen Array? Wenn ja, warum sollten wir das nicht umsetzen? Lassen Sie uns ein solches assoziatives Array schaffen, bei dem jeder Schlüssel – das geordnete Paar von Ganzzahlen – einem Wert zugeordnet wird, der eine ganze oder fließende Zahl darstellt, das Gewicht der Kante angibt. In C++ ist es sinnvoll, diese Struktur auf der Basis des Containers std::map (std::map<std::pair, int> oder std::map<std::pair, double>) zu implementieren, oder std::multimap, wenn mehrere Kanten vorgesehen sind. Und so haben wir eine Struktur für die Speicherung von Graphen, die weniger Speicherplatz benötigt als 'matrixbasierte' Strukturen, an denen mehrere Schleifen und Kanten existieren können und die nicht einmal strenge Anforderungen an die Nichtnegativität der Knotenindizes hat (ich weiß nicht, wem das nutzt, aber trotzdem).
4. Datenstrukturen, egal wie sehr man es auch möchte, es fehlt doch etwas.
Es ist wahr: Bei der Lösung bestimmter Aufgaben kann es notwendig werden, Kanten eines Graphen mit bestimmten Eigenschaften zu versehen und diese entsprechend zu speichern. Wenn es möglich ist, diese Eigenschaften eindeutig auf Ganzzahlen zu reduzieren, können solche 'Graphen mit zusätzlichen Eigenschaften' unter Verwendung erweiterter Versionen von Nachbarschaftsvektoren und assoziativen Nachbarschaftsarrays gespeichert werden.
Angenommen, wir haben einen ungewichteten Graphen, bei dem für jede Kante beispielsweise 2 zusätzliche Eigenschaften gespeichert werden müssen, die durch ganze Zahlen definiert sind. In diesem Fall kann sein Adjazenzvektor als eine geordnete Menge von nicht "Pairs", sondern "Quartetten" von ganzen Zahlen dargestellt werden (a[2i], a[2i+1], a[2i+2], a[2i+3]…), wobei a[2i+2] und a[2i+3] die Eigenschaften der entsprechenden Kante definieren. Für einen Graphen mit ganzzahligen Kantengewichten bleibt die Reihenfolge im Allgemeinen ähnlich (der Unterschied besteht darin, dass die Eigenschaften nach dem Gewicht der Kante folgen und durch die Elemente a[2i+3] und a[2i+4] definiert werden, während die Kante selbst nicht durch 4, sondern durch 5 geordnete Zahlen dargestellt wird). Bei einem Graphen mit nicht-ganzzahligen Kantengewichten können die Eigenschaften in dessen ungewichteten Teil aufgezeichnet werden.
Bei der Verwendung von Adjazenzlisten für Graphen mit ganzzahligen Kantengewichten kann als Wert nicht nur eine einzelne Zahl, sondern auch ein Array (Vektor) von Zahlen angegeben werden, das neben dem Kantengewicht auch alle anderen benötigten Merkmale beschreibt. Ein Nachteil im Fall von nicht-ganzzahligen Gewichten besteht darin, dass das Merkmal als Gleitkommazahl angegeben werden muss (ja, das ist ein Nachteil, aber wenn es nicht allzu viele solcher Merkmale gibt und man sie nicht zu 'komplex' als double angibt, könnte das durchaus machbar sein). In C++ können also erweiterte Adjazenzlisten wie folgt definiert werden: std::map<std::pair, std::vector> oder std::map<std::pair, std::vector>, wobei das erste Element im 'Wert-Vektor-zum-Schlüssel' das Kantengewicht darstellt und die weiteren die numerischen Bezeichnungen der Merkmale sind.
Literatur:
Über Graphen und Algorithmen allgemein:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algorithmen: Konstruktion und Analyse, 2. Auflage: Übers. aus dem Engl. – Moskau: Williams Verlag, 2011.
2. Harary, Frank. Graphentheorie. Moskau: Mir, 1973.
Bericht des Autors über den Adjazenzvektor und das assoziative Adjazenzarray:
3. Tschernoukhov S.A. Adjazenzvektor und assoziatives Adjazenzarray als Methoden zur Darstellung und Speicherung von Graphen / S.A. Tschernoukhov. Adjacency vector and adjacency map as data structures to represent a graph // Sammlung von Artikeln der internationalen wissenschaftlich-praktischen Konferenz „Probleme der Umsetzung innovativer Entwicklungen und Wege zu deren Lösung“ (Saratow, 14.09.2019). – Sterlitamak: AMI, 2019, S. 65-69
Nützliche Internetquellen zu diesem Thema:
4.
5.
Quelle: habr.com
