Datenstrukturen zum Speichern von Diagrammen: eine Überprüfung vorhandener und zwei „fast neuer“ Diagramme

Hallo.

In dieser Notiz habe ich beschlossen, die wichtigsten Datenstrukturen aufzulisten, die zum Speichern von Diagrammen in der Informatik verwendet werden, und ich werde auch über ein paar weitere solcher Strukturen sprechen, die sich für mich irgendwie „kristallisiert“ haben.

Also, fangen wir an. Aber nicht von Anfang an – ich denke, wir alle wissen bereits, was ein Graph ist und was er ist (gerichtet, ungerichtet, gewichtet, ungewichtet, mit oder ohne mehrere Kanten und Schleifen).

So lass uns gehen. Welche Möglichkeiten für Datenstrukturen zur „Graphspeicherung“ haben wir?

1. Matrixdatenstrukturen

1.1 Adjazenzmatrix. Die Adjazenzmatrix ist eine Matrix, bei der die Zeilen- und Spaltenüberschriften den Nummern der Scheitelpunkte des Diagramms entsprechen und der Wert jedes seiner Elemente a(i,j) durch das Vorhandensein oder Fehlen von Kanten zwischen den Scheitelpunkten bestimmt wird i und j (es ist klar, dass eine solche Matrix für einen ungerichteten Graphen symmetrisch sein wird, oder wir können uns 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 bis j festgelegt werden (wenn es keine solche Kante gibt, dann ist a(i,j)= 0), und für gewichtete Graphen auch durch das Gewicht (Gesamtgewicht) der genannten Kanten.

1.2 Inzidenzmatrix. Auch in diesem Fall wird unser Graph in einer Tabelle gespeichert, in der in der Regel die Zeilennummern den Nummern seiner Eckpunkte und die Spaltennummern vornummerierten Kanten entsprechen. Wenn ein Scheitelpunkt und eine Kante miteinander inzident sind, wird ein Wert ungleich Null in die entsprechende Zelle geschrieben (bei ungerichteten Diagrammen wird 1 geschrieben, wenn Scheitelpunkt und Kante inzident sind, bei orientierten Diagrammen - „1“, wenn die Kante „verlässt“ den Scheitelpunkt und „-1“, wenn es darin „einschließt“ (es ist leicht zu merken, da das „Minus“-Zeichen auch in der Zahl „-1“ „eingeschlossen“ zu sein scheint). Für gewichtete Diagramme können Sie anstelle von 1 und -1 wiederum das Gesamtgewicht der Kante angeben.

2. Aufzählungsdatenstrukturen

2.1 Adjazenzliste. Nun, hier scheint alles einfach zu sein. Jeder Scheitelpunkt des Diagramms kann im Allgemeinen einer beliebigen Aufzählungsstruktur (Liste, Vektor, Array usw.) zugeordnet werden, die die Nummern aller Scheitelpunkte speichert, die an den angegebenen Scheitelpunkt angrenzen. Bei gerichteten Graphen fügen wir einer solchen Liste nur die Scheitelpunkte hinzu, zu denen es eine „gerichtete“ Kante von einem Merkmalsscheitelpunkt gibt. Bei gewichteten Diagrammen wird die Implementierung komplexer sein.

2.2 Liste der Rippen. Eine recht beliebte Datenstruktur. Die Liste der Kanten ist, wie Captain Obviousness uns sagt, eigentlich eine Liste von Kanten des Graphen, von denen jede durch den Startscheitelpunkt und den Endscheitelpunkt spezifiziert wird (bei ungerichteten Graphen ist die Reihenfolge hier nicht wichtig, für die Vereinheitlichung ist dies jedoch möglich). Verwenden Sie verschiedene Regeln, z. B. die Angabe der Scheitelpunkte in aufsteigender Reihenfolge) und der Gewichtung (nur für gewichtete Diagramme).

Sie können sich die oben aufgeführten Matrixlisten genauer (und mit Abbildungen) ansehen, z. B. hier.

2.3 Adjazenz-Array. 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 (entsprechend der Anzahl der Eckpunkte des Graphen) Elemente eines solchen Arrays enthalten die Startindizes desselben Arrays, von dem aus alle an den gegebenen Eckpunkten angrenzenden Eckpunkte in einer Reihe geschrieben werden.

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

3. Adjazenzvektor und assoziatives Adjazenzarray

Es stellte sich heraus, dass der Autor dieser Zeilen, der kein professioneller Programmierer war, sich aber regelmäßig mit Diagrammen beschäftigte, sich am häufigsten mit Kantenlisten befasste. Tatsächlich ist es praktisch, wenn der Graph mehrere Schleifen und Kanten hat. Deshalb schlage ich vor, bei der Entwicklung der klassischen Kantenlisten auf deren „Entwicklung/Verzweigung/Modifikation/Mutation“ zu achten, nämlich: den Adjazenzvektor und das assoziative Adjazenzarray.

3.1 Adjazenzvektor

Fall (a1): ungewichteter Graph

Wir nennen einen Adjazenzvektor für einen ungewichteten Graphen eine geordnete Menge einer geraden Anzahl von ganzen Zahlen (a[2i], a[2i+1],..., wobei i die Nummer c 0 hat), in der jedes Zahlenpaar ist a[2i], a[2i+1 ] gibt eine Graphkante zwischen den Eckpunkten a[2i] bzw. a[2i+1] an.
Dieses Aufzeichnungsformat enthält keine Informationen darüber, ob der Graph gerichtet ist (beide Optionen sind möglich). Bei Verwendung des Digraphenformats wird davon ausgegangen, 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 Aufzeichnung von Scheitelpunkten gelten (z. B. dass der Scheitelpunkt mit dem niedrigeren Wert der ihm zugewiesenen Zahl zuerst kommt).

In C++ empfiehlt es sich, mit std::vector einen Adjazenzvektor anzugeben, daher der Name dieser Datenstruktur.

Fall (a2): ungewichteter Graph, Kantengewichte sind ganzzahlig

Analog zum 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 die Nummer c 0 hat), wobei jedes „Triplett“ der Zahlen a[3i], a[3i+1], a[3i+2] eine Kante des Graphen zwischen Eckpunkten mit der Nummer a[3i] angibt. bzw. a[3i+1] und der Wert a [3i+2] ist das Gewicht dieser Kante. Ein solcher Graph kann auch gerichtet sein oder nicht.

Fall (b): ungewichteter Graph, nicht ganzzahlige Kantengewichte

Da es beispielsweise nicht möglich ist, heterogene Elemente in einem Array (Vektor) zu speichern, ist die folgende Implementierung möglich. Der Graph wird in einem Vektorpaar gespeichert, wobei der erste Vektor der Adjazenzvektor des Graphen ohne Angabe der Gewichte ist und der zweite Vektor die entsprechenden Gewichte enthält (mögliche Implementierung für C++: std::pair ). Für eine Kante, die durch ein Scheitelpunktpaar unter den Indizes 2i, 2i+1 des ersten Vektors definiert ist, ist das Gewicht also gleich dem Element unter dem Index i des zweiten Vektors.

Nun, warum ist das notwendig?

Nun, der Autor dieser Zeilen fand es sehr nützlich, um eine Reihe von Problemen zu lösen. Aus formaler Sicht ergeben sich folgende Vorteile:

• Der Adjazenzvektor ist wie jede andere „aufzählende“ Struktur recht kompakt, benötigt weniger Speicher als die Adjazenzmatrix (für dünn besetzte Graphen) und ist relativ einfach zu implementieren.
• Die Eckpunkte des Graphen können grundsätzlich auch mit negativen Zahlen markiert werden. Was ist, wenn eine solche „Perversion“ nötig ist?
• Diagramme können mehrere Kanten und mehrere Schleifen mit unterschiedlichen Gewichten (positiv, negativ, sogar Null) enthalten. Hier gibt es keine Einschränkungen.
• Sie können Kanten auch unterschiedliche Eigenschaften zuweisen – mehr dazu finden Sie in Abschnitt 4.

Es muss jedoch zugegeben werden, dass diese „Liste“ keinen schnellen Zugriff auf den Rand bedeutet. Und hier kommt das Associative Adjacency Array zur Rettung, das weiter unten besprochen wird.

3.2 Assoziatives Adjazenz-Array

Wenn also der Zugriff auf eine bestimmte Kante, ihr Gewicht und andere Eigenschaften für uns von entscheidender Bedeutung sind und der Speicherbedarf es uns nicht erlaubt, die Adjazenzmatrix zu verwenden, dann überlegen wir uns, wie wir den Adjazenzvektor ändern können, um dieses Problem zu lösen. Der Schlüssel ist also eine Kante des Graphen, die als geordnetes Paar ganzer Zahlen angegeben werden kann. Wie sieht das aus? Ist es nicht ein Schlüssel in einem assoziativen Array? Und wenn ja, warum setzen wir es nicht um? Lassen Sie uns ein assoziatives Array haben, in dem jedem Schlüssel – einem geordneten Paar ganzer Zahlen – ein Wert zugeordnet wird – eine ganze Zahl oder eine reelle Zahl, die das Gewicht der Kante angibt. In C++ empfiehlt es sich, diese Struktur auf Basis des std::map-Containers (std::map , int> oder std::map , double>) oder std::multimap, wenn mehrere Kanten erwartet werden. Nun, wir haben eine Struktur zum Speichern von Graphen, die weniger Speicher beansprucht als „Matrix“-Strukturen, Graphen mit mehreren Schleifen und Kanten definieren kann und nicht einmal strenge Anforderungen an die Nichtnegativität von Scheitelpunktzahlen stellt (ich weiß es nicht). Wer braucht das, aber trotzdem).

4. Die Datenstrukturen sind voll, aber es fehlt etwas

Und es stimmt: Wenn wir eine Reihe von Problemen lösen, müssen wir möglicherweise den Kanten des Diagramms bestimmte Eigenschaften zuweisen und diese 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“ mithilfe erweiterter Versionen des Adjazenzvektors und des assoziativen Adjazenzarrays zu speichern.

Lassen Sie uns also einen ungewichteten Graphen haben, für den für jede Kante beispielsweise zwei zusätzliche durch Ganzzahlen angegebene Merkmale gespeichert werden müssen. In diesem Fall ist es möglich, seinen Adjazenzvektor als eine geordnete Menge nicht von „Paaren“, sondern von „Quartetten“ von ganzen Zahlen (a[2i], a[2i+2], a[1i+2], a) zu definieren [2i+2]…), wobei a[3i+2] und a[2i+2] die Eigenschaften der entsprechenden Kante bestimmen. Bei einem Diagramm mit ganzzahligen Kantengewichten ist die Reihenfolge im Allgemeinen ähnlich (der einzige Unterschied besteht darin, dass die Attribute dem Kantengewicht folgen und durch die Elemente a[3i+2] und a[3i+2] angegeben werden). , und die Kante selbst wird nicht mit 4, sondern mit 4 geordneten Zahlen angegeben. Und für einen Graphen mit nicht ganzzahligen Kantengewichten können die Features in seine ungewichtete Komponente geschrieben werden.

Bei Verwendung eines assoziativen Adjazenz-Arrays für Diagramme mit ganzzahligen Kantengewichten ist es möglich, als Wert nicht eine einzelne Zahl, sondern ein Array (Vektor) von Zahlen anzugeben, die zusätzlich zum Gewicht einer Kante alle anderen erforderlichen Werte angeben Merkmale. Gleichzeitig besteht eine Unannehmlichkeit bei nicht ganzzahligen Gewichten darin, dass ein Vorzeichen mit einer Gleitkommazahl angegeben werden muss (ja, das ist eine Unannehmlichkeit, aber wenn es nicht so viele solcher Vorzeichen gibt und Sie dies nicht tun). Stellen Sie sie nicht zu „knifflig“ doppelt ein, dann ist es vielleicht nichts. Dies bedeutet, dass in C++ erweiterte assoziative Adjazenz-Arrays wie folgt definiert werden können: std::map , std::vector> oder std::map , std::vector, in dem der erste Wert im „Schlüsselwertvektor“ das Gewicht der Kante ist, und dann werden die numerischen Bezeichnungen ihrer Eigenschaften angegeben.

Литература:

Über Graphen und Algorithmen im Allgemeinen:

1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithmen: Konstruktion und Analyse, 2. Auflage: Trans. aus dem Englischen – M.: Williams Publishing House, 2011.
2. Harari Frank. Graphentheorie. M.: Mir, 1973.
Der Bericht des Autors über denselben Vektor und dasselbe assoziative Array von Adjazenzen:
3. Chernoukhov S.A. Adjazenzvektor und assoziatives Adjazenzarray als Möglichkeiten zur Darstellung und Speicherung von Graphen / SA Chernouhov. Adjazenzvektor und Adjazenzkarte als Datenstrukturen zur Darstellung eines Diagramms // Sammlung von Artikeln der Internationalen Wissenschafts- und Praxiskonferenz „Probleme bei der Umsetzung der Ergebnisse innovativer Entwicklungen und Wege zu ihrer Lösung“ (Saratov, 14.09.2019. September 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Nützliche Online-Quellen zum Thema:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Source: habr.com