Datenstrukturen für die Grafikspeicherung: eine Überprüfung bestehender und zwei "fast neuer"

Hallo an alle.

In dieser Notiz habe ich beschlossen, die wichtigsten Datenstrukturen aufzulisten, die zum Speichern von Graphen in der Informatik verwendet werden, und auch über einige andere Strukturen zu sprechen, die sich irgendwie aus mir herauskristallisiert haben.

Also fangen wir an. Aber nicht von Anfang an - ich denke, was ein Graph ist und was er ist (orientiert, nicht orientiert, gewichtet, ungewichtet, mit mehreren Kanten und Schleifen oder ohne sie), wissen wir alle bereits.

Also lass uns gehen. Welche Möglichkeiten haben wir für Datenstrukturen zur "Graphspeicherung"?

1. Matrixdatenstrukturen

1.1 Adjazenzmatrix. Die Adjazenzmatrix ist eine Matrix, in der die Zeilen- und Spaltenüberschriften den Nummern der Eckpunkte des Graphen entsprechen und der Wert jedes seiner Elemente a (i, j) durch das Vorhandensein oder Fehlen von Kanten zwischen den Eckpunkten i und j bestimmt wird (es ist klar, dass eine solche Matrix für einen ungerichteten Graphen gilt wird symmetrisch sein, gut, oder Sie können zustimmen, dass wir alle Werte nur über der Hauptdiagonale speichern). Für ungewichtete Graphen kann a (i, j) durch die Anzahl der Kanten von i bis j angegeben werden (wenn es keine solche Kante gibt, dann ist a (i, j) = 0), und für gewichtete durch das Gewicht (Gesamtgewicht) der genannten Kanten.

1.2 Die Inzidenzmatrix. In diesem Fall wird unser Diagramm auch in einer Tabelle gespeichert, in der in der Regel die Zeilennummern den Nummern seiner Eckpunkte und die Spaltennummern vornummerierten Kanten entsprechen. Wenn der Scheitelpunkt und die Kante aufeinander treffen, wird ein Wert ungleich Null in die entsprechende Zelle geschrieben (für ungerichtete Diagramme wird 1 für den Fall des Scheitelpunkts und der Kante geschrieben, für orientierte Diagramme "1", wenn die Kante den Scheitelpunkt "verlässt" und "-1", wenn dies der Fall ist es "tritt ein" (es ist ziemlich leicht zu merken, da das Minuszeichen auch in der Zahl "-1" "enthalten" zu sein scheint)). Bei gewichteten Diagrammen können Sie anstelle von 1 und -1 auch das Gesamtgewicht der Kante angeben.

2. Aufzählungsdatenstrukturen

2.1 Adjazenzliste. Nun, alles scheint einfach zu sein. Im Allgemeinen kann jeder Scheitelpunkt eines Graphen einer beliebigen Aufzählungsstruktur (Liste, Vektor, Array, ...) zugeordnet werden, in der die Nummern aller Scheitelpunkte neben diesem gespeichert werden. Bei orientierten Graphen werden nur Scheitelpunkte aufgelistet, bei denen es eine "gerichtete" Kante vom Scheitelpunktattribut gibt. Bei gewichteten Diagrammen ist die Implementierung komplexer.

2.2 Liste der Rippen. Ziemlich beliebte Datenstruktur. Die Liste der Kanten ist, wie Captain Evidence uns sagt, eine Liste der Kanten des Diagramms, von denen jede durch einen anfänglichen Scheitelpunkt, einen Endscheitelpunkt, definiert ist (für ungerichtete Diagramme ist die Reihenfolge hier nicht wichtig, obwohl verschiedene Regeln für die Vereinheitlichung verwendet werden können, z. B. Scheitelpunkte in der Reihenfolge angeben aufsteigend) und Gewicht (nur für gewichtete Diagramme).

Informationen zu den oben aufgeführten Matrixlisten finden Sie (z. B. hier ) ausführlicher.

2.3 Adjazenzarray. Nicht die häufigste Struktur. Im Kern handelt es sich um eine Form des "Packens" von Adjazenzlisten in eine Aufzählungsstruktur (Array, Vektor). Die ersten n (nach Anzahl der Graphenscheitelpunkte) Elemente eines solchen Arrays enthalten Startindizes desselben Arrays, ab denen alle angrenzenden Scheitelpunkte in einer Reihe darin geschrieben werden.

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

3. Adjazenzvektor und assoziatives Adjazenzarray

Es kam vor, dass der Autor dieser Zeilen, der kein professioneller Programmierer war, sondern sich regelmäßig mit Graphen befasste, sich am häufigsten mit Kantenlisten befasste. In der Tat ist es praktisch, wenn der Graph mehrere Schleifen und Kanten hat. Und jetzt, bei der Entwicklung der klassischen Kantenlisten, schlage ich vor, auf ihre „Entwicklung / Verzweigung / Modifikation / Mutation“ zu achten, nämlich auf den Adjazenzvektor und das assoziative Array der Adjazenz.

3.1 Adjazenzvektor

Fall (A1): Ungewichtete Anzahl

Wir werden den Adjazenzvektor für einen ungewichteten Graphen eine geordnete Menge einer geraden Anzahl von ganzen Zahlen (a [2i], a [2i + 1], ..., wobei i mit c 0 nummeriert ist) bezeichnen, in der jedes Zahlenpaar a [2i], a [2i +1] definiert die Kante des Graphen zwischen den Eckpunkten a [2i] und a [2i + 1].
Dieses Aufnahmeformat enthält keine Informationen darüber, ob das Diagramm ausgerichtet ist (beide Optionen sind möglich). Bei Verwendung des Digraphenformats wird angenommen, dass die Kante von a [2i] nach a [2i + 1] gerichtet ist. Im Folgenden: Bei ungerichteten Diagrammen können bei Bedarf die Anforderungen für die Reihenfolge der Aufzeichnung von Scheitelpunkten angewendet werden (z. B. so, dass der Scheitelpunkt mit dem niedrigeren Wert der ihm zugewiesenen Zahl an erster Stelle steht).

In C ++ ist es ratsam, den Adjazenzvektor mit std :: vector anzugeben, aus dem der Name dieser Datenstruktur ausgewählt wurde.

Fall (a2): ungewichteter Graph, ganzzahlige Kantengewichte

In Analogie zu Fall (a1) nennen wir den Adjazenzvektor 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 ist mit c 0) nummeriert, wobei jedes "Triplett" der Zahlen a [3i], a [3i + 1], a [3i + 2] die Kante des Graphen zwischen den Eckpunkten unter den Zahlen a [3i] bzw. a [3i + 1] definiert und Der Wert von a [3i + 2] ist das Gewicht dieser Kante. Ein solcher Graph kann auch entweder orientiert sein oder nicht.

Fall (b): ungewichteter Graph, nicht ganzzahlige Kantengewichte

Da die heterogenen Elemente nicht in einem Array (Vektor) gespeichert werden können, ist beispielsweise die folgende Implementierung möglich. Der Graph wird in einem Vektorpaar gespeichert, wobei der erste Vektor der Adjazenzvektor des Graphen ohne Angabe von Gewichten ist und der zweite Vektor die entsprechenden Gewichte enthält (eine mögliche Implementierung für C ++ ist: std :: pair <std :: vector, std :: vector>). Somit ist für eine Kante, die durch ein Paar von Eckpunkten unter den Indizes 2i, 2i + 1 des ersten Vektors definiert ist, das Gewicht gleich dem Element unter dem Index i des zweiten Vektors.

Nun, warum ist das notwendig?

Für den Autor dieser Zeilen zur Lösung einer Reihe von Problemen schien dies sehr nützlich zu sein. Aus formaler Sicht wird es solche Vorteile geben:

• Der Adjazenzvektor ist wie jede andere "Aufzählungs" -Struktur kompakt genug, benötigt weniger Speicher als die Adjazenzmatrix (für spärliche Graphen) und ist relativ einfach zu implementieren.
• Die Eckpunkte des Graphen können grundsätzlich mit negativen Zahlen markiert werden. Plötzlich ist auch eine solche „Perversion“ erforderlich.
• Diagramme können mehrere Kanten und mehrere Schleifen mit unterschiedlichen Gewichten (positiv, negativ, sogar null) enthalten. Hier gibt es keine Einschränkungen.
• Und Rippen können unterschiedliche Eigenschaften zugewiesen werden - dazu siehe Absatz 4.

Ich muss jedoch zugeben, dass dieser „Listot“ keinen schnellen Zugang zur Rippe bedeutet. Und hier beeilt sich das assoziative Adjazenz-Array, um zu helfen, worüber - unten.

3.2 Assoziatives Adjazenzarray

Wenn für uns der Zugriff auf eine bestimmte Kante, deren Gewicht und andere Eigenschaften von entscheidender Bedeutung ist und die Speicheranforderungen die Verwendung einer Adjazenzmatrix nicht zulassen, sollten wir uns überlegen, wie Sie den Adjazenzvektor ändern können, um dieses Problem zu lösen. Der Schlüssel ist also die Kante des Graphen, die als geordnetes Paar von ganzen Zahlen definiert werden kann. Wie sieht es aus? Könnte es ein Schlüssel in einem assoziativen Array sein? Und wenn ja, warum setzen wir das nicht um? Lassen Sie uns ein solches assoziatives Array haben, in dem jeder Schlüssel - ein geordnetes Paar von Ganzzahlen - einem Wert zugeordnet wird - einer Ganzzahl oder einer reellen Zahl, die das Gewicht der Kante angibt. In C ++ ist es ratsam, diese Struktur auf der Basis des std :: map-Containers zu implementieren (std :: map <std :: pair <int, int>, int> oder std :: map <std :: pair <int, int>, double>). oder std :: multimap, wenn mehrere Kanten angenommen werden. Nun, und hier haben wir eine Struktur zum Speichern von Graphen, die weniger Speicher benötigt als "Matrix" -Strukturen, Graphen mit mehreren Schleifen und Kanten definieren können und auch ohne strenge Anforderungen an die Nicht-Negativität von Scheitelpunktzahlen (ich weiß nicht, wer sie benötigt). aber immer noch).

4. Datenstrukturen zumindest "fluten", aber etwas fehlt

Und die Wahrheit ist: Wenn wir eine Reihe von Problemen lösen, müssen wir möglicherweise den Rändern des Diagramms einige Attribute zuweisen und sie entsprechend speichern. Wenn es möglich ist, diese Merkmale eindeutig auf ganze Zahlen zu reduzieren, ist es möglich, solche "Graphen mit zusätzlichen Merkmalen" unter Verwendung erweiterter Versionen des Adjazenzvektors und des assoziativen Adjazenzarrays zu speichern.

Lassen Sie uns also ein ungewichtetes Diagramm haben, für das für jede Kante beispielsweise zwei zusätzliche Zeichen gespeichert werden müssen, die durch Ganzzahlen angegeben werden. In diesem Fall ist es möglich, seinen Adjazenzvektor als eine geordnete Menge von nicht "Paaren", sondern "Quartetten" von ganzen Zahlen (a [2i], a [2i + 1], a [2i + 2], a [2i + 3] anzugeben. .), wobei a [2i + 2] und a [2i + 3] die Merkmale der entsprechenden Kante bestimmen. Bei einem Diagramm mit ganzzahligen Kantengewichten ist die Reihenfolge im Allgemeinen ähnlich (der einzige Unterschied besteht darin, dass die Vorzeichen dem Kantengewicht folgen und durch die Elemente a [2i + 3] und a [2i + 4] gegeben sind und die Kante selbst angegeben wird nicht 4, sondern 5 bestellte Nummern). Bei einem Diagramm mit nicht ganzzahligen Kantengewichten können die Attribute in die ungewichtete Komponente geschrieben werden.

Wenn Sie ein assoziatives Adjazenzarray für Diagramme mit ganzzahligen Kantengewichten verwenden, können Sie nicht eine einzelne Zahl, sondern ein Array (einen Vektor) von Zahlen angeben, das neben dem Kantengewicht alle anderen erforderlichen Attribute angibt. Gleichzeitig besteht die Unannehmlichkeit für den Fall von nicht ganzzahligen Gewichten darin, dass ein Zeichen mit einer Gleitkommazahl angegeben werden muss (ja, dies ist eine Unannehmlichkeit, aber wenn es nicht so viele solcher Zeichen gibt und Sie sie nicht zu "knifflig" doppelt setzen, kann es nichts sein). . In C ++ können erweiterte assoziative Adjazenz-Arrays wie folgt definiert werden: std :: map <std :: pair <int, int>, std :: vector> oder std :: map <std :: pair <int, int>, std :: vector, wobei der erste Wert in "vector-value-by-key" das Gewicht der Kante ist und dann die numerischen Bezeichnungen ihrer Merkmale gefunden werden.

Referenzen:

Über Grafiken und Algorithmen im Allgemeinen:

1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithmen: Konstruktion und Analyse, 2. Auflage: Per. aus dem Englischen - M.: Williams Verlag, 2011.
2. Harari Frank. Graphentheorie. M.: Mir, 1973.
Der Bericht des Autors über denselben Vektor und dieselbe assoziative Nachbarschaft:
3. Chernoukhov S.A. Adjazenzvektor und assoziatives Adjazenzarray als Mittel zur Darstellung und Speicherung von Graphen / SA Chernouhov. Adjazenzvektor und Adjazenzkarte als Datenstrukturen zur Darstellung eines Graphen // Sammlung von Artikeln der Internationalen wissenschaftlichen und praktischen Konferenz "Probleme bei der Umsetzung der Ergebnisse innovativer Entwicklungen und Lösungswege" (Saratov, 14. September 2019). - Sterlitamak: AMI, 2019, p. 65-69
Nützliche Internetquellen zum Thema:
4.prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html