Datenstrukturen zur Speicherung von Graphen: Überblick über bestehende und zwei "fast neue"

Hallo zusammen.

In dieser Notiz habe ich beschlossen, die wichtigsten Datenstrukturen aufzulisten, die in der Informatik zur Speicherung von Graphen verwendet werden, und ich werde auch über noch ein paar andere solcher Strukturen sprechen, die sich mir irgendwie "herauskristallisiert" haben.

Also, fangen wir an. Aber nicht von Anfang an – ich denke, dass wir alle bereits wissen, was ein Graph ist und welche Arten es gibt (gerichtete, ungerichtete, gewichtete, ungewichtete, mit mehreren Kanten und Schleifen oder ohne diese).

Also, los geht's. Welche Optionen für Datenstrukturen zur "Graphenspeicherung" haben wir.

1. Matriziale Datenstrukturen

1.1 Adjazenzmatrix. Die Adjazenzmatrix ist eine Matrix, in der die Kopfzeilen der Zeilen und Spalten den Nummern der Graphknoten entsprechen, und der Wert jedes Elements a(i,j) bestimmt sich durch das Vorhandensein oder Fehlen von Kanten zwischen den Knoten i und j (es ist klar, dass eine solche Matrix für ungerichtete Graphen symmetrisch sein wird, oder man kann vereinbaren, dass wir alle Werte nur über der Hauptdiagonalen speichern). Für ungewichtete Graphen kann a(i,j) durch die Anzahl der Kanten von i nach j definiert werden (wenn es keine solche Kante gibt, dann ist a(i,j) = 0), und für gewichtete Graphen ebenfalls – mit dem Gewicht (Gesamtgewicht) der genannten Kanten.

1.2 Inzidenzmatrix. In diesem Fall wird unser Graph ebenfalls in einer Tabelle gespeichert, in der in der Regel die Zeilennummern den Nummern seiner Knoten entsprechen und die Spaltennummern den vorher nummerierten Kanten. Wenn ein Knoten und eine Kante inzident zueinander sind, wird in die entsprechende Zelle ein nicht-null Wert eingetragen (für ungerichtete Graphen wird 1 bei Inzidenz zwischen Knoten und Kante eingetragen, für gerichtete „1“, wenn die Kante „aus“ dem Knoten „herausgeht“ und „-1“, wenn sie „hineingeht“ (das merkt man sich leicht, da das Zeichen „Minus“ auch wie eine „Eingabe“ in die Zahl „-1“ wirkt)). Für gewichtete Graphen kann man wieder anstelle von 1 und -1 das Gesamtgewicht der Kante angeben.

2. Aufzählbare Datenstrukturen

2.1 Nachbarschaftsliste. Hier ist alles einfach. Jeder Knoten eines Graphen kann im Allgemeinen mit einer beliebigen Auflistungsstruktur (Liste, Vektor, Array, ...) korreliert werden, in der die Nummern aller benachbarten Knoten gespeichert werden. Für gerichtete Graphen fügen wir nur die Knoten in solch eine Liste ein, zu denen eine "gerichtete" Kante vom Merkmal-Knoten führt. Bei gewichteten Graphen wird die Implementierung komplexer sein.

2.2 List der Kanten. Eine recht populäre Datenstruktur. Die Kantenliste, wie uns Kapitän Offensichtlich verrät, stellt eigentlich die Liste der Kanten des Graphen dar, von denen jede durch einen Startknoten, einen Endknoten (bei ungerichteten Graphen ist die Reihenfolge hier nicht wichtig, obwohl man zur Vereinheitlichung verschiedene Regeln verwenden kann, z. B. die Knoten in aufsteigender Reihenfolge angeben) und ein Gewicht (nur für gewichtete Graphen) definiert ist.

Eine detailliertere Betrachtung der oben genannten Listen-Matrizen ist, zum Beispiel, hier zu finden: hier.

2.3 Nachbarschaftsarray. Nicht die am häufigsten anzutreffende Struktur. Im Grunde stellt es eine Form der "Verpackung" von Nachbarschaftslisten in eine einzige Auflistungsstruktur (Array, Vektor) dar. Die ersten n (je nach Anzahl der Knoten im Graphen) Elemente dieses Arrays enthalten die Startindizes des gleichen Arrays, von denen aus alle benachbarten Knoten in aufeinanderfolgender Reihenfolge aufgezeichnet sind.

Hier fand ich die verständlichste (für mich) Erklärung: ejuo.livejournal.com/4518.html

3. Nachbarschaftsvektor und Assoziatives Nachbarschaftsarray

Es kam so, dass der Verfasser dieser Zeilen, der kein professioneller Programmierer ist, aber gelegentlich mit Graphen zu tun hatte, häufig mit Kantenlisten gearbeitet hat. Tatsächlich ist es praktisch, wenn es im Graphen Mehrfachschleifen und Kanten gibt. Und so lade ich ein, auch den "Weiterentwicklungen/Abzweigungen/Modifikationen/Mutationen" von klassischen Kantenlisten und zwar dem Nachbarschaftsvektor und dem assoziativen Nachbarschaftsarray Aufmerksamkeit zu schenken.

3.1 Nachbarschaftsvektor

Fall (a1): ungewichteter Graph

Wir bezeichnen einen Nachbarschaftsvektor für einen ungewichteten Graphen als geordnete Menge einer geraden Anzahl von ganzen Zahlen (a[2i], a[2i+1],…, wobei i von 0 nummeriert wird), in der jedes Zahlenpaar a[2i], a[2i+1] eine Kante des Graphen zwischen den Knoten a[2i] und a[2i+1] definiert.
Dieses Aufzeichnungsformat enthält keine Informationen darüber, ob der Graph gerichtet ist (beide Varianten sind möglich). Bei der Verwendung des Formats für einen gerichteten 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 Nummer zuerst kommt).

In C++ ist es sinnvoll, den Nachbarvektor mit std::vector zu definieren, daher wurde dieser Name für die Datenstruktur gewählt.

Fall (a2): ungewichteter Graph, Kanten haben ganze Zahlen als Gewichte

Analog zum Fall (a1) nennen wir den Nachbarvektor für einen gewichteten Graphen mit ganzzahligen Kantengewichten eine geordnete Menge (dynamisches Array) von Zahlen (a[3i], a[3i+1], a[3i+2],… wobei i von 0 nummeriert wird), wobei jedes 'Triplet' von Zahlen a[3i], a[3i+1], a[3i+2] eine Kante des Graphen zwischen den Knoten mit den Nummern a[3i] und a[3i+1] definiert, während der Wert a[3i+2] das Gewicht dieser Kante ist. Ein solcher Graph kann sowohl gerichtet als auch ungerichtet sein.

Fall (b): ungewichteter Graph, Kanten haben keine ganzzahligen Gewichte

Da in einem Array (Vektor) keine heterogenen Elemente gespeichert werden können, könnte folgende Implementierung möglich sein. Der Graph wird in einem Paar von Vektoren gespeichert, wobei der erste Vektor der Nachbarvektor des Graphen ohne Gewichtsangaben ist, während der zweite Vektor die entsprechenden Gewichte enthält (eine mögliche Implementierung für C++: std::pair). Somit wird für eine Kante, die durch ein Paar von Knoten mit den Indizes 2i, 2i+1 im ersten Vektor definiert ist, das Gewicht dem Element mit dem Index i im zweiten Vektor entsprechen.

Aber wozu ist das nötig?

Nun, dem Verfasser dieser Zeilen schien es für die Lösung einer Reihe von Aufgaben ziemlich nützlich. Und aus formaler Sicht gibt es folgende Vorteile:

• Der Nachbarvektor ist, wie jede andere 'auflistbare' Struktur, recht kompakt, benötigt weniger Speicher als die Adjazenzmatrix (für spärliche Graphen) und lässt sich relativ einfach implementieren.
• Die Knoten eines Graphen können prinzipiell auch mit negativen Zahlen gekennzeichnet werden. Falls das auch einmal nötig sein sollte.
• Graphen können mehrere Kanten und Schlaufen enthalten, und zwar mit unterschiedlichen Gewichten (positive, negative, sogar null). Hier gibt es keine Einschränkungen.
• Außerdem können den Kanten verschiedene Eigenschaften zugewiesen werden – aber dazu siehe Punkt 4.

Allerdings muss man eingestehen, dass dieser "Listenansatz" keinen schnellen Zugriff auf eine Kante ermöglicht. Hier kommt das Assoziative Nachbarschaftsarray zur Hilfe, darüber später.

3.2 Assoziatives Nachbarschaftsarray

Wenn der Zugriff auf eine bestimmte Kante, ihr Gewicht und andere Eigenschaften kritisch für uns ist und die Anforderungen an den Speicher die Verwendung einer Adjazenzmatrix nicht zulassen, müssen wir darüber nachdenken, wie wir den Nachbarschaftsvektor ändern können, um dieses Problem zu lösen. Der Schlüssel ist die Kante des Graphen, die als geordnete Paarung von Ganzzahlen dargestellt werden kann. Was erinnert uns das? Ist es nicht der Schlüssel in einem assoziativen Array? Wenn ja, warum sollten wir das nicht umsetzen? Lassen Sie uns ein solches assoziatives Array schaffen, bei dem jedem Schlüssel – der geordneten Paarung von Ganzzahlen – ein Wert – eine ganze oder reelle Zahl, die das Gewicht der Kante angibt – zugeordnet ist. In C++ ist es sinnvoll, diese Struktur auf der Grundlage des Containers std::map (std::map <std::pair , int> oder std::map <std::pair , double>) oder std::multimap zu implementieren, falls mehrere Kanten angenommen werden. So haben wir eine Struktur zur Speicherung von Graphen erhalten, die weniger Speicherplatz benötigt als "Matrixstrukturen", die Graphen mit mehreren Schleifen und Kanten darstellen kann und sogar keine strengen Anforderungen an die Nichtnegativeität der Knotennummern hat (ich weiß nicht, wer das braucht, aber trotzdem).

4. Datenstrukturen, egal wie man sie anwendet, es fehlt etwas

Und tatsächlich: Bei der Lösung verschiedener Probleme kann es notwendig sein, den Kanten eines Graphen bestimmte Merkmale zuzuweisen und diese entsprechend zu speichern. Wenn es möglich ist, diese Merkmale eindeutig auf ganze Zahlen zu reduzieren, können solche "Graphen mit zusätzlichen Merkmalen" unter Verwendung erweiterter Versionen des Nachbarschaftsvektors und des assoziativen Nachbarschaftsarrays gespeichert werden.

Angenommen, wir haben einen ungewichteten Graphen, für dessen jede Kante wir zum Beispiel 2 zusätzliche Merkmale speichern müssen, die durch ganze Zahlen definiert sind. In diesem Fall kann sein Adjazenzvektor als eine geordnete Menge nicht von "Paaren", sondern von "Vierteln" ganzer Zahlen (a[2i], a[2i+1], a[2i+2], a[2i+3]…) angegeben werden, wobei a[2i+2] und a[2i+3] die Merkmale der entsprechenden Kante definieren. Für einen Graphen mit ganzzahligen Kantengewichten ist die Reihenfolge grundsätzlich ähnlich (der einzige Unterschied besteht darin, dass die Merkmale nach dem Gewicht der Kante folgen und durch die Elemente a[2i+3] und a[2i+4] definiert werden, während die Kante nicht durch 4, sondern durch 5 geordnete Zahlen beschrieben wird). Und für einen Graphen mit nicht-ganzzahligen Kantengewichten können die Merkmale in seiner ungewichteten Komponente aufgezeichnet werden.

Bei der Verwendung eines assoziativen Adjazenzarrays für Graphen mit ganzzahligen Kantengewichten ist es möglich, als Wert nicht eine einzelne Zahl, sondern ein Array (Vektor) von Zahlen anzugeben, das zusätzlich zum Gewicht der Kante alle anderen erforderlichen Merkmale angibt. Ein Nachteil im Fall von nicht-ganzzahligen Gewichten besteht darin, dass das Merkmal als Fließkommazahl angegeben werden muss (ja, das ist ein Nachteil, aber wenn es nicht so viele solcher Merkmale gibt und wenn man sie nicht zu "kompliziert" in double angibt, kann es akzeptabel sein). Das bedeutet, dass in C++ erweiterte assoziative Adjazenzarrays folgendermaßen definiert werden können: std::map <std::pair < int, int>, std::vector> oder std::map <std::pair < int, int>, std::vector, wobei das erste Element im "Wert-Vektor-für-den-Schlüssel" das Gewicht der Kante ist und danach die numerischen Bezeichnungen ihrer Merkmale angeordnet sind.

Literatur:

Über Graphen und Algorithmen im Allgemeinen:

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algorithmen: Konstruktion und Analyse, 2. Auflage: Übers. aus dem Engl. – M.: Verlagshaus "Williams", 2011.
2. Harari, Frank. Graphentheorie. M.: Mir, 1973.
Der Vortrag des Autors über genau diesen Vektor und das assoziative Adjazenzarray:
3. Tschernoukhov S.A. Adjazenzvektor und Adjazenzliste als Datenstrukturen zur Darstellung eines Graphen // Sammelband der Internationalen wissenschaftlich-praktischen Konferenz "Probleme der Implementierung der Ergebnisse innovativer Entwicklungen und deren Lösungen" (Saratow, 14.09.2019). – Sterlitamak: AMI, 2019, S. 65-69
Nützliche Internetquellen zum Thema:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Quelle: habr.com